剑指 Offer 25. 合并两个排序的链表

21. 合并两个有序链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

输入输出

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

基本思路

  • 指针法：设置伪头结点，依次链接两个链表中较小的值，最后将剩余的部分接上。时间O(m+n)空间O(1)。
  • 递归法：去掉比较过的节点，和剩余的丢进去递归。时间空间都是O(m+n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
递归举例：1->4->5->null, 1->2->3->6->null

//(1,1):代表第一次进入递归函数，并且从第一个口进入，并且记录进入前链表的状态
merge(1,1): 1->4->5->null, 1->2->3->6->null
	merge(2,2): 4->5->null, 1->2->3->6->null
		merge(3,2): 4->5->null, 2->3->6->null
			merge(4,2): 4->5->null, 3->6->null
				merge(5,1): 4->5->null, 6->null
					merge(6,1): 5->null, 6->null
						merge(7): null, 6->null
						return l2
					l1.next --- 5->6->null, return l1
				l1.next --- 4->5->6->null, return l1
			l2.next --- 3->4->5->6->null, return l2
		l2.next --- 2->3->4->5->6->null, return l2
	l2.next --- 1->2->3->4->5->6->null, return l2
l1.next --- 1->1->2->3->4->5->6->null, return l1

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

//指针移动放入新链表
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(0), cur = res;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return res.next;
    }
}
//递归
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val <= l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}