leetcode第21题，合并两个有序链表。采用双指针的算法来完成。

LeetCode 21合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

1输入：l1 = [1,2,4], l2 = [1,3,4]
2输出：[1,1,2,3,4,4]

示例 2：

1输入：l1 = [], l2 = []
2输出：[]

示例 3：

1输入：l1 = [], l2 = [0]
2输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

思路

可以同之前数组一样采用双指针的形式

  1. 每个链表头部有一个指针
  2. 比较双指针所在的值，会出现三种结果。如果相等，默认取链表2中的元素，P指向这个元素，并且链表P和指针往后移动一位；如果不相等，取指针指向小的那位，并且指针往后移动一位。
  3. 直到两个指针全部移动完成

解题

 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11class Solution {
12    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
13        if(list1 == null) return list2;
14        if(list2 == null) return list1;
15        ListNode list3 = new ListNode(0);
16        ListNode p = list3;
17        while(list1 != null && list2 != null)
18        {
19            if(list1.val >= list2.val)
20            {
21                p.next = list2;
22                list2 = list2.next;
23            }else
24            {
25                p.next = list1;
26                list1 = list1.next;
27            }
28            p = p.next;
29        }
30
31        if(list1 == null)
32        {
33            p.next = list2;
34        }
35
36        if(list2 == null)
37        {
38            p.next = list1;
39        }
40
41        return list3.next;
42    }
43}

递归操作

两条链表合并问题经过一次转换为短链表的合并问题

可以同之前数组一样采用双指针+递归的形式

  1. 每个链表头部有一个指针
  2. 比较双指针所在的值，会出现三种结果。如果相等，默认取链表2中的元素，P指向这个元素，并且链表P和指针往后移动一位；如果不相等，取指针指向小的那位，并且指针往后移动一位。
  3. 后移之后这个问题转换成两个短链表之间的合并问题（递归）
  4. 直到短链表合并出现一条链表，然后两个指针全部移动完成
 1/**
 2 * Definition for singly-linked list.
 3 * public class ListNode {
 4 *     int val;
 5 *     ListNode next;
 6 *     ListNode() {}
 7 *     ListNode(int val) { this.val = val; }
 8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9 * }
10 */
11class Solution {
12    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
13        if(list1 == null) return list2;
14        if(list2 == null) return list1;
15        if(list1.val >= list2.val)
16        {
17            //前面的list2.next代表list2的下一个指向为mergeTwoLists的ListNode
18            //后面的list2.next代表list2的指针向后移动一位
19            list2.next = mergeTwoLists(list1, list2.next);
20            return list2;
21        }else
22        {
23            list1.next = mergeTwoLists(list1.next, list2);
24            return list1;
25        }
26    }
27}