欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

23、合并两个排序的链表——剑指offer

程序员文章站 2024-02-14 23:51:40
...

合并两个排序的链表

问题描述:合并两个排序的链表

23、合并两个排序的链表——剑指offer

    首先考察基本功,两种方法,一种是用递归的方法,一种非递归的方法。

    本方法思想:当前指针指向两个链表头部比较小的那个

23、合并两个排序的链表——剑指offer

持续更新...

代码附下

Java实现:

package 合并两个排序的链表;
/**
 * 一种递归方法 一种非递归方法
 * @author user
 *
 */

23、合并两个排序的链表——剑指offer

方法1:非递归
class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}
public class MergeList {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(3);
        ListNode n3 = new ListNode(5);
        ListNode n4 = new ListNode(7);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        ListNode n11 = new ListNode(2);
        ListNode n22 = new ListNode(10);
        ListNode n33 = new ListNode(11);
        ListNode n44 = new ListNode(12);
        n11.next = n22;
        n22.next = n33;
        n33.next = n44;
        ListNode head = merge(n1, n11);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    public static ListNode merge(ListNode n1, ListNode n11) {
        ListNode head1 = n1;
        ListNode head2 = n11;
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode head = null;
        if (head1.val < head2.val) {
            head = head1;
            head1 = head1.next;
        } else {
            head = head2;
            head2 = head2.next;
        }
        ListNode cur = head;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
                cur = cur.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
                cur = cur.next;
            }
        }
        if (head1 == null && head2 != null) {
            cur.next = head2;
        }
        if (head2 == null && head1 != null) {
            cur.next = head1;
        }
        return head;
    }

方法2:递归

public static ListNode RecMerge(ListNode n1, ListNode n11) {
        ListNode head1 = n1;
        ListNode head2 = n11;
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        ListNode head = null;
        if (head1.val < head2.val) {
            head = head1;
            head.next = RecMerge(head1.next, head2);
        } else {
            head = head2;
            head.next = RecMerge(head1, head2.next);
        }
        return head;
    }
}

持续更新...欢迎赞赏!23、合并两个排序的链表——剑指offer

主页:https://blog.csdn.net/ustcer_93lk/article/details/80374008

如果有问题,欢迎大家留言,有更好的方法也期待大家告知。