数据结构与算法

合并两个排序的链表

略

题目:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的.例如输入1,3,5,7和2,4,6,8.合并后成为1,2,3,4,5,6,7,8.

分析

  从两个链表的头结点开始比较,例如题目上的例子,比较1和2,当然是1比较小,然后就把1拿出来,组成新链表的第一个结点,然后就剩下3,5,7和2,4,6,8这两个链表,同理,比较3和2,2比较小,就把2拿出了,放到新链表的后面,新链表变成1,2.以此类推到两个链表的头结点为空时停止.这里使用递归来实现.

代码实现

代码如下:

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)
            return list2;
        else if(list2 == null)
            return list1;
        ListNode mergedHead = null;
        
        if(list1.val < list2.val){
            mergedHead = list1;
            mergedHead.next = Merge(list1.next,list2);
        } else {
            mergedHead = list2;
            mergedHead.next = Merge(list1,list2.next);
        }
        return mergedHead;
    }
}

总结

  1. 要考虑的问题是:输入空链表时代码是否可以和合并成的新链表必须要递增排序并且不可断裂.
  2. 复习时可以尝试把递归改成循环.