【算法100天 | 19】链表拆分、深拷贝

1、根据某一值x将链表分为三段

将链表分为三段：小于x、等于x、大于x。合并返回。

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int v) {
        val = v;
    }
}
1
2
3
4
5
6
7
8

方法一：使用容器

使用一个数组保存链表，然后基于快速排序的思想，排序数组。

空间复杂度：O(n)，时间复杂度：O(n)。

/**
 * 方法一：使用容器
 * 空间复杂度：O(n)，时间复杂度：O(4n)
 * 参考快速排序的方式
 */
public static ListNode listPartition1(ListNode head, int pivot) {
    if (head == null) {
        return head;
    }
    int n = 0;
    ListNode cur = head;
    while (cur != null) {
        n++;
        cur = cur.next;
    }
    ListNode[] nodes = new ListNode[n];
    cur = head;
    for (int i = 0; i < n; i++) {
        nodes[i] = cur;
        cur = cur.next;
    }

    // sort nodes
    arrayPartition(nodes, pivot);
    for (int i = 1; i < n; i++) {
        nodes[i - 1].next = nodes[i];
    }
    return nodes[0];
}

private static void arrayPartition(ListNode[] nodes, int pivot) {
    int n = nodes.length;
    int small = -1;
    int big = n;
    int index = 0;
    while (index < big) {
        if (nodes[index].val < pivot) {
            swap(nodes, ++small, index);
        } else if (nodes[index].val == pivot) {
            index++;
        } else {
            swap(nodes, --big, index);
        }
    }
}

private static void swap(ListNode[] nodes, int a, int b) {
    ListNode temp = nodes[a];
    nodes[a] = nodes[b];
    nodes[b] = temp;
}
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
49
50
51

方法二：使用几个变量

使用六个变量分别维护 小于x的head、tail，等于x的head、tail，大于x的head、tail。遍历链表维护这六个变量。

空间复杂度：O(1)，时间复杂度：O(n)

/**
 * 方法二：使用几个变量
 * 空间复杂度：O(1)，时间复杂度：O(4n)
 */
public static ListNode listPartition2(ListNode head, int pivot) {
    if (head == null) {
        return head;
    }
    ListNode sHead = null;
    ListNode sTail = null;
    ListNode eHead = null;
    ListNode eTail = null;
    ListNode bHead = null;
    ListNode bTail = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = null;
        if (head.val < pivot) {
            if (sHead == null) {
                sHead = head;
            } else {
                sTail.next = head;
            }
            sTail = head;
        } else if (head.val == pivot) {
            if (eHead == null) {
                eHead = head;
            } else {
                eTail.next = head;
            }
            eTail = head;
        } else {
            if (bHead == null) {
                bHead = head;
            } else {
                bTail.next = head;
            }
            bTail = head;
        }
        head = next;
    }
    // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头

    if (sTail != null) {
        sTail.next = eHead;
        /**
         * 尽量让eTail不为null
         *     1）有等于区域，eT -> 等于区域的尾结点
         *     2）无等于区域，eT -> 小于区域的尾结点
         */
        eTail = eTail == null ? sTail : eTail;
    }
    if (eTail != null) {
        eTail.next = bHead;
    }

    return sHead != null ? sHead : (eHead != null ? eHead : bHead);
}
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
49
50
51
52
53
54
55
56
57
58

2、链表深拷贝

每个链表节点有两个指针，一个指向next，一个随机指向任何一个节点；

public static class Node {
    public int value;
    public Node next;
    public Node rand;

    public Node(int data) {
        this.value = data;
    }
}
1
2
3
4
5
6
7
8
9

方法一：使用Map维护老节点和新节点的对应关系

使用Map维护老节点和新节点的对应关系，再遍历一遍老节点，维护新节点。

空间复杂度：O(n)，时间复杂度：O(n)

public static Node copyListWithRand1(Node head) {
    Map<Node, Node> map = new HashMap<>();
    Node cur = head;
    while (cur != null) {
        map.put(cur, new Node(cur.value));
        cur = cur.next;
    }
    cur = head;
    while (cur != null) {
        map.get(cur).next = map.get(cur.next);
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：调整链表

针对每一个链表中的老节点，都新建一个node放在其next指针上，然后将node.next指向老节点的原next。

比如：

// 1 -> 2 -> 3
// 1 -> 1' -> 2 -> 2' -> 3 -> 3'
1
2

然后再遍历两边组装后的链表，分别维护random指针、next指针。

空间复杂度：O(1)，时间复杂度：O(n)

public static Node copyListWithRand2(Node head) {
    if (head == null) {
        return null;
    }
    Node cur = head;
    Node next;
    // 1 -> 2
    // 1 -> 1' -> 2
    while (cur != null) {
        // cur == 老节点， next == 老节点的下一个
        next = cur.next;
        cur.next = new Node(cur.value);
        cur.next.next = next;
        cur = next;
    }

    // handle random pointer
    cur = head;
    Node curCopy;
    while (cur != null) {
        // cur 老
        // cur.next 新 copy
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.rand = cur.rand != null ? cur.rand.next : null;
        cur = next;
    }

    // handler next pointer
    cur = head;
    Node res = head.next;
    while (cur != null) {
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.next = next != null ? next.next : null;
        cur = next;
    }
    return res;
}
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