原地合并两个有序链表并去重

Posted on

题目描述： 给定两个有序的，不含有重复值的链表，请将这两个有序链表进行原地合并，并且保证合并后的链表中，不包含重复数据.

输入输出示例：

  • Example 1 : 1 -> 3 -> 5 和 1 -> 2 -> 4，合并结果：1 -> 2 -> 3 -> 4 -> 5
  • Example 2 : 2 -> 5 -> 7 和 1 -> 3，合并结果：1 -> 2 -> 3 -> 5 -> 7

题目分析

1
2
3
4
5
6
7
8
9
// 结点结构
static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
  1. 给定两个有序的，不包含重复数据的链表，我们在进行合并的时候，就有可能存在重复数据，所以需要进行去重操作；
  2. 这两个有序链表需要进行原地合并，所以，我们不能像一般的方法一样，去新建一个头结点. 然后，分别去比较和扫描两个有序链表，将结点中的较小数值的数据 new 出 新的Node ，放在头结点之后.
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
44
45
46
47
48
public Node mergeSortedListWithoutDuplicates(Node node1, Node node2) {
        //1.首先，根据两个结点情况判空，高效返回
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }
        //2. 新建一个结点，指向结点值较小的那个
        Node head = (node1.val <= node2.val) ? node1 : node2;
        //3. 创建两个指针，动态的指向 node1 和 node2
        Node prev = head;
        Node point = null;

        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                point = node1;
                node1 = node1.next;
            } else {
                point = node2;
                node2 = node2.next;
            }
            if (prev.val != point.val) {
                prev.next = point;
                prev = point;
            }
        }

        //处理多余结点
        while (node2 != null) {
            if (prev.val != node2.val) {
                prev.next = node2;
                prev = node2;
            }
            node2 = node2.next;
        }

        while (node1 != null) {
            if (prev.val != node1.val) {
                prev.next = node1;
                prev = node1;
            }
            node1 = node1.next;
        }
//        将最后一个结点的下一个结点置位 null
        prev.next = null;
        return head;
    }