甲乙小朋友的房子

甲乙小朋友很笨，但甲乙小朋友不会放弃

0%

算法-链表

发表于 更新于 分类于

链表

链表考点

  • 会不会写程序 - 类、指针、引用等

知识点

  • 链表中的Dummy Node
  • 基本链表技能
  • 链表的Two Pointers(Fast-slow pointers)

入门题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void print(){
  for(ListNode node = head; node != null; node = node.next){
    System.out.print(node.val);
    System.out.print("->");
  }
  System.out.println("null");
}

void main(){
  ListNode node1 = new ListNode(1);
  ListNode node2 = new ListNode(2);
  ListNode node3 = new ListNode(3);
  
  ListNode head = node1;
  
  node1.next = node2;
  node2.next = node3;
  
  print(head); // 输出啥？
  
  node1 = node2;
  
  print(head); // 输出啥？
}

答案：

1
2
3
1->2->3->null

1->2->3->null

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
初始：

  n1      n2        n3
[1,-]--> [2,-]--> [3,null]
===================================
head = n1 : 

 head
  n1      n2        n3
[1,-]--> [2,-]--> [3,null]

sizeof(head) = 4 
===================================
n1 = n2 : 

 head     n1
          n2        n3
[1,-]--> [2,-]--> [3,null]

例题

例题1，Remove Duplicates from Sorted List

将有序链表去重

例题2，Remove Duplicates from Sorted List II

将有序链表中的全部重复元素删除

思路：使用dummy node

当链表结构发生变化时，使用dummy node

1
2
3
4
5
6
7
8
9
10
11
12
套路：伪节点

// 伪节点
          head
 dummy     n1       n2         n3
 [,-]--> [1,-]--> [2,-]--> [3,null]

ListNode dummy = new ListNode(0);
dummy.next = head;


return dummy.next;

删除节点p方式：

开始写了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode dummy = new ListNode(0);
dummy.next = head;

// 前继节点和当前节点
ListNode prev = dummy;
ListNode curt = head;

while(null != curt){
  if(null != curt.next && curt.val == curt.next.val){// 如果重复了
    int val = curt.val;
    while(curt != null && curt.val == val){
      curt = curt.next;
    }
    // curt == null or curt.val != val
    prev.next = curt;
  }else{ // 如果不重复
    prev = curt;
    curt = curt.next;
  }
}
return dummy.next; // 这里需要注意一下

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode deleteDuplicates(ListNode head) {
  if(null == head)return head;
  ListNode dummy = new ListNode(0);
  dummy.next = head;

  ListNode prev = dummy;
  ListNode curt = head;
  while (null != curt){
    if(null != curt.next && curt.val == curt.next.val){
      int temp = curt.val;
      curt = curt.next;
      while (null != curt && curt.val == temp){
        curt = curt.next;
      }
      prev.next = curt;
    }else {
      prev = curt;
      curt = curt.next;
    }
  }
  return dummy.next;
}

例题，Remove Linked List Elements

删除链表中的某个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode removeElements(ListNode head, int val) {
        if(null == head)return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curt = head;

        while (null != curt){
            if(curt.val == val){
                curt = curt.next;
                prev.next = curt;
            }else {
                prev = curt;
                curt = curt.next;
            }
        }
        return dummy.next;
    }

例题3，Reverse Linked List

将链表反转

1
2
3
4
5
6
7
8
9
10
11
ListNode prev = null;
ListNode curt = head;

while( null != curt){
  ListNode temp = curt.next;
  curt.next = prev;
  prev = curt;
  curt = temp;
}

return prev;

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode reverseList(ListNode head) {
  if(null == head){return head;}
  ListNode curt = head;
  ListNode prev = null;
  ListNode temp;
  while (null != curt){
    temp = curt.next;
    curt.next = prev;
    if(null != temp) {
      prev = curt;
      curt = temp;
    }else {
      break;
    }
  }
  return curt; // 如果这里返回prev的话就不用中间的判断temp是否为空了
}

例题4，Reverse Linked List II

将一个链表的m到n反转

1
2
3
4
5
拆解问题

1. 寻找第m个点
2. 将m-n反转
3. 把整个链表连成一个链表！(如下图所示)

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
if(m >= n || head == null){
  return head;
}

ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode prev = dummy;

//find m-th
for(int i = 1 ; i < m ; ++i){
if(null == head){
	return null;
	}else{
	head = head.next;
	}
}
ListNode premNode = head;
if(null == head){
  return null;
}
ListNode mNode = head.next;

// reverse m - n
ListNode nNode = mNode, postnNode = mNode.next;
for(int i = m; i < n; i++){
  if(null == postnNode){
    return null;
  }
  ListNode temp = postnNode.next;
  postnNODE.next = nNode;
  nNode = postnNode;
  postnNode = temp;
}

// connect m-1 -> n, m - > n+1
mNode.next = postnNode;
premNode.next = nNode;

return dummy.next;

代码：

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
public ListNode reverseBetween(ListNode head, int m, int n) {
  ListNode curt = head;
  ListNode prev = null;
  // find m
  for(int i = 1 ; i < m ; ++i){
    if(null == curt.next) return null;
    prev = curt;
    curt = curt.next;
  }
  ListNode mNodePrev = prev;
  ListNode mNode = curt;
  // reverse m - n
  ListNode next = curt.next;
  n = n - m + 1;
  while (null != curt && n > 0){
    next = curt.next;
    curt.next = prev;
    prev = curt;
    curt = next;
    --n;
  }
  ListNode nNode = prev;
  mNode.next = next;
  if(null == mNodePrev){
    return nNode;
  }
  mNodePrev.next = nNode;
  return head;
}

例题5，Reverse Nodes in k-Group

将链表按照k大小的组，反转。如果最后不够k个，则保持原样。

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
public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curt = head;

        int c;
        while (null != curt) {
            c = k;
            ListNode firstNodePrev = prev;
            ListNode firstNode = curt;
            if(null == curt) break;
            while (null != curt && c > 0) {
                ListNode next = curt.next;
                curt.next = prev;
                prev = curt;
                curt = next;
                --c;
            }
            if(c > 0){ // 末尾保持原样
                c = k - c;
                while (c > 0){
                    ListNode last = prev.next;
                    prev.next = curt;
                    curt = prev;
                    prev = last;
                    --c;
                }
                return dummy.next;
            }
            firstNodePrev.next = prev;
            firstNode.next = curt;

            prev = firstNode;
        }
        return dummy.next;
    }

例题6，Partition List

要求把小于x的元素放到链表前面

思路：排两个队，小的一队，大的一队

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
if(null == head){
  return null;
}

ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy, right = rightDummy; // 左右队伍的尾巴

while(null != head){
  if(head.val < x){
    left.next = head;
    left = head;
  }else{
    right.next = head;
    right = head;
  }
  head = head.next;
}

right.next = null;
left.next = rightDummy.next;
return leftDummy.next;

代码：

public ListNode partition(ListNode head, int x) {
        ListNode leftTail = new ListNode(0),
                rightTail = new ListNode(0);

        ListNode leftHead = leftTail, rightHead = rightTail;

        while (null != head){
            if(head.val < x){
                leftTail.next = head;
                leftTail = leftTail.next;
            }else {
                rightTail.next = head;
                rightTail = rightTail.next;
            }
            head = head.next;
        }
        rightTail.next = null;
        // 合并
        leftTail.next = rightHead.next;
        return leftHead.next;
    }

Basic Skills in Linked List

增、删、反转、合并、中点

Fast-slow Pointers问题

1
2
3
4
5
6
7
8
9
10
11
链表中点的骚操作

private ListNode getMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

应用场景：

  1. 链表中点
  2. 移除倒数第N个元素
  3. Linked List Cycle I，II
  4. Rotate List

例题7，Sort List

用O(nlogn)的时间和空间复杂度排序链表

思路：n log n的排序 - 快速排序、归并排序、堆排序

排序 快速排序 归并排序
思路 先整体有序，后局部（左右有序）有序 先局部（左右有序）有序，后整体有序
不稳定排序（原来在前面的不一定还在前面） 稳定排序-同样的key保持原来的顺序
时间 \(O(nlogn --- O(n^2))\) \(O(nlogn)\)
空间 O(1) 数组上O(n)，链表上\(O(1)\)

这道题可以用快排，但其实归并排序更好写

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
关键点：怎么取中点？

取中点骚操作：

private ListNode findMiddle(ListNode head){
	ListNode slow = head, fast = head.next;
	// 当fast走完的时候，slow就是中点
    while(null != fast && null != fast.next){
    	fast = fast.next.next;
    	slow = slow.next;
    }
    return slow;
}


合并：

private ListNode merge(ListNode head1, ListNode head2){
	ListNode dummy = new ListNode(0);
	ListNode tail = dummy;
    while(null != head1 && null != head2){
    	if(head1.val < head2.val){
          tail.next = head1;
          head1 = head1.next;
        }else{
          tail.next = head2;
          head2 = head2.next;
        }
        tail = tail.next;
    }
    if(null != head1){
      tail.next = head1;
      }else if(null != head2){
      tail.next = head2;
      }
    
    return dummy.next;

}


主函数

public ListNode sortList(ListNode head){
  if(null != head || null != head.next){
    return head;
  }
  // 找中点
  ListNode mid = findMiddle(head);

  // 分解问题
  ListNode right = sortList(mid.next);
  mid.next = null;
  ListNode left = sortList(head);

  // 合并问题
  return merge(left,right);
}

代码

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
private ListNode getMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (null != fast && null != fast.next){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode merge(ListNode right, ListNode left){
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        dummy.next = head;
        while (null != right && null != left){
            if(right.val < left.val){
                head.next = right;
                right = right.next;
            }else {
                head.next = left;
                left = left.next;
            }
            head = head.next;
        }
        if(null != right){
            head.next = right;
        }else if(null != left){
            head.next = left;
        }
        return dummy.next;
    }
    public ListNode sortList(ListNode head) {
        //归并排序
        if(null == head) return null;
        if(null == head.next) return head;
        // 获取中值
        ListNode mid = getMiddle(head);
        // 分解问题
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        // 合并
        return merge(left,right);
    }

例题8，Reorder List

将链表 L0→L1→…→Ln-1→Ln, 重排序为L0→Ln→L1→Ln-1→L2→*L**n*-2→…

思路：

  1. 找中点
  2. 中点右半部分reverse
  3. 合并
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
private ListNode getMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (null != fast && null != fast.next){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    private ListNode reverse(ListNode head){
        ListNode last = null;
        while (null != head){
            ListNode temp = head.next;
            head.next = last;
            last = head;
            head = temp;
        }
        return last;
    }
    public void reorderList(ListNode head) {
        if(null == head || null == head.next) return;
        // 找中点
        ListNode mid = getMiddle(head);
        // 反转 mid - end
        ListNode right = reverse(mid.next);
        mid.next = null;
        // 合并
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        boolean fromRight = false;
        while (null != head && null != right) {
            ListNode temp = head.next;
            head.next = right;
            right = right.next;
            head.next.next = temp;
            head = head.next.next;
        }
    }

例题9，Linked List Cycle

判断链表里有没有环形

暴力方法：用hash表

骚操作：快指针和慢指针如果相遇了，就有环

代码：

1
2
3
4
5
6
7
8
9
10
11
public boolean hasCycle(ListNode head) {
        if(null == head || null == head.next) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (null != fast && null != fast.next){
            if(fast == slow){return true;}
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

例题10，Linked List Cycle II

如果有环，找到环的入口

骚操作：快指针和慢指针如果相遇了，就有环。相遇之后，再让head和slow分别开始，每次走一步。相遇后一定是环入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode detectCycle(ListNode head) {
        if(null == head || null == head.next) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while (null != fast && null != fast.next){
            if(fast == slow){
                slow = slow.next;
                while (true){
                    if(slow == head)
                        return slow;
                    slow = slow.next;
                    head = head.next;
                }
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return null;
    }

例题11，Rotate List

  1. 循环移动
  2. 找到倒数第k个
  3. 断开连上就好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public ListNode rotateRight(ListNode head, int k) {
    if(null == head || null == head.next) return head;
    int n = getLength(head);
    // 寻找倒数第k个
    k = k % n;
    if(k == 0) return head;
    ListNode fast = head;
    for(int i = 0 ; i < k ; ++i){
        fast = fast.next;
    }
    ListNode slow = head;
    while (null != fast && null != fast.next){
        slow = slow.next;
        fast = fast.next;
    }
    // 注意这里的技巧，此时fast = tail
    ListNode right = slow.next;
    slow.next = null;
    fast.next = head;

    return right;
}

例题12，Merge k Sorted Lists

三种方法：

  1. 堆，维护当前每个list的head。复杂度\(Nlogk\)

  2. 分治法。复杂度\(Nlogk\)--每个数都经过\(logk\) 次合并

    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

             *
            / \
          /     *
        /      / \
      *       /   *
     / \     /   / \ 
    1   2   3   4   5

    将两个 k/2 的链表组，合并为一个链表 

    	public ListNode mergeKLists(ListNode[] lists){
            if(lists.length == 0){
                return null;
            }
            return mergeHelper(lists, 0, lists.length - 1);
        }
        private ListNode mergeHelper(ListNode[] lists, int start, int end){

            if(end == start) return lists[start];
            int mid = start + (end - start) / 2;
            ListNode left = mergeHelper(lists, start, mid);
            ListNode right = mergeHelper(lists,mid + 1, end);
            return mergeTwoLists(left,right);
        }
        private ListNode mergeTwoLists(ListNode list1, ListNode list2){
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            while (null != list1 && null != list2){
                if(list1.val < list2.val){
                    tail.next = list1;
                    list1 = list1.next;
                }else{
                    tail.next = list2;
                    list2 = list2.next;
                }
                tail = tail.next;
            }
            if(null != list1){
                tail.next = list1;
            }else if(null != list2){
                tail.next = list2;
            }
            return dummy.next;
        }

  3. 两两合并，复杂度\(Nlogk\)

    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

             9
           /  \
          8    \
        /   \   \
      6       7  \
     / \     / \   \ 
    1   2   3   4   5
               
               
    public ListNode mergeKLists(List<ListNode> lists){
      if(lists.size() == 0){
        return null;
      }
      while(lists.size() > 1){
        List<ListNode> new_lists = new ArrayList<ListNode>();
        for (int i = 0; i + 1 < lists.size(); i += 2) {
                    ListNode merged_list = merge(lists.get(i), lists.get(i+1));
                    new_lists.add(merged_list);
         }
        if (lists.size() % 2 == 1) {
          new_lists.add(lists.get(lists.size() - 1));
        }
        lists = new_lists;
      }
      return lists.get(0);
    }

    private ListNode merge(ListNode list1, ListNode list2){
      ListNode dummy = new ListNode(0);
      ListNode tail = dummy;
      while(list1 != null && list2 != null){
        if(list1.val < list2.val){
          tail.next = list1;
          tail = list1;
          list1 = list1.next;
        }else{
          tail.next = list2;
          tail = list2;
          list2 = list2.next;
        }
      }
      if (list1 != null) {
                tail.next = list1;
      } else {
        tail.next = list2;
      }
      return dummy.next;
    }

    例题13，Copy List with Random Pointer

    ​

    1 -> 2 -> 3 -> 4...

    然后每个点都有一个random指针，随机指

    要求将这个random list 深拷贝一次

    方法一，依次拷贝node.next,用一个哈希表存储每个[oldNode,newNode]

    1

    方法二，骚操作，优化，用O(1)的空间复杂度

    刚才我们存储的是映射关系，老节点->新节点，用巧妙的方式存储这个关系

    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
    1 -> 2 -> 3 -> 4 -> null

    变成
      
    1 -> 1` -> 2 -> 2` -> 3 -> 3` -> 4 -> 4` -> null
      
    a.next.next -->保留了原来链表的关系
    a.next      -->新的链表

    那么如果链表中有random指针，如下

    __            __________
    ↑↓           ↑          ↓
    1  ->  1` -> 2 -> 2` -> 3 -> 3` -> 4 -> 4` -> null
      
    那么复制这个random关系即可！！

    然后再把这个链表拆开即可！

    总结：
    1. copy next
    2. copy random
    3. split

    代码：
    public RandomListNode copyRandomList(RandomListNode head) {
            if(null == head) return null;
            // copy next
            RandomListNode curr = head;

            while(null != curr){
                RandomListNode copy = new RandomListNode(curr.label);
                copy.next = curr.next;
                curr.next = copy;
                curr = curr.next.next;
            }
            // copy random
            curr = head;
            while(null != curr){
                if(curr.random != null){
                    curr.next.random = curr.random.next;
                }
                curr = curr.next.next;
            }
            // split
            RandomListNode dummy = head.next;
            while (null != head){
                RandomListNode temp = head.next;
                head.next = temp.next;
                head = head.next;
                if (temp.next != null) {
                    temp.next = temp.next.next;
                }
            }
            return dummy;

        }

Swap Nodes in Pairs

将链表两两反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void swap(ListNode obj,ListNode prev){
        prev.next = obj.next;
        obj.next = prev.next.next;
        prev.next.next = obj;
    }
    public ListNode swapPairs(ListNode head) {
        if(null == head || null == head.next) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        while (null != head && null != head.next){
            swap(head,prev);
            head = head.next;
            prev = prev.next.next;
        }
        return dummy.next;
    }

Delete Node in a Linked List

1
2
3
4
5
6
public void deleteNode(ListNode node) {
        if(node != null && node.next != null) {
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

Palindrome Linked List

判断一个list是不是回文串

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
private ListNode getMiddle(ListNode head){
    ListNode fast = head.next;
    ListNode slow = head;
    while (null != fast && null != fast.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
private ListNode reverse(ListNode head){
    ListNode last = null;
    while (null != head){
        ListNode temp = head.next;
        head.next = last;
        last = head;
        head = temp;
    }
    return last;
}
public boolean isPalindrome(ListNode head) {
    if(null == head || null == head.next) return true;
    // 找中点
    ListNode middle = getMiddle(head);
    ListNode right = middle.next;
    middle.next = null;
    // 将right反转
    right = reverse(right);
    while (null != right && null != head && right.val == head.val){
        right = right.next;
        head = head.next;
    }
    if((null == head && null == right)||
            (null == head.next && null == right)||
            (null == right.next && null == head)){
        return true;
    }
    return false;
}

Odd Even Linked List

将链表的奇数位放前面，偶数位放后面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode oddEvenList(ListNode head) {
    if(null == head || null == head.next) return head;
    ListNode oddDummy = new ListNode(0);
    ListNode evenDummy = new ListNode(0);
    oddDummy.next = head;
    evenDummy.next = head.next;
    ListNode odd = head;
    ListNode even = head.next;
    while (null != even && null != even.next){
        odd.next = even.next;
        even.next = odd.next.next;
        odd = odd.next;
        even = even.next;
    }
    odd.next = evenDummy.next;
    return oddDummy.next;
}

Split Linked List in Parts

很无聊的题。

将一个链表分为k个部分，每个部分的长度差不得超过1，且前面的长度不得小于后面的长度。

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
private int getLength(ListNode root){
    int length = 0;
    while (null != root){
        root = root.next;
        ++length;
    }
    return length;
}
public ListNode[] splitListToParts(ListNode root, int k) {
    int length = getLength(root);
    int n = length/k;
    int m = length % k;
    ListNode[] results = new ListNode[k];
    int pos = 0;
    while (null != root){
        int i = m > 0 ? n : n - 1;
        m-=1;
        ListNode dummy = new ListNode(0);
        dummy.next = root;
        while (i > 0){
            root = root.next;
            --i;
        }
        ListNode temp = root.next;
        root.next = null;
        root = temp;
        results[pos] = dummy.next;
        ++pos;
    }
    while (pos < k){
        results[pos] = null;
        ++pos;
    }
    return results;
}

Insertion Sort List

实现链表的插入排序

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
public ListNode insertionSortList(ListNode head) {
        if(null == head || null == head.next) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curt = head;
        while (null != curt && null != curt.next){
            if(curt.next.val >= curt.val){
                curt = curt.next;
            }else {
                // 将curt.next插入到前面
                ListNode prev = dummy.next;
                ListNode insert = curt.next;
                if(dummy.next.val >= insert.val)
                    prev = dummy;
                else {
                    while (prev.next.val < insert.val) {
                        prev = prev.next;
                    }
                }
                // 将curt.next插到prev后面
                curt.next = curt.next.next;
                ListNode prevNext = prev.next;
                prev.next = insert;
                insert.next = prevNext;
            }
        }
        return dummy.next;
    }

总结

  • 凡是链表结构发生变化的，都需要Dummy Node
  • 链表常用基本功：
    • 反转 reverse
    • 归并 merge
    • 找中点 median
    • 增删查改
  • Linked List Cycle , 知道怎么做，理解
  • Linked List Cycle II，知道怎么做，课后分析一下为什么，背下程序
  • Copy List with Random Pointers
    • 能写出hash map方法
    • 优化方法要能正确实现
  • Merge k Sorted Arrays
    • k路归并一定要掌握
    • 三种方式分别实现，并熟练理解和掌握
    • 顺便做一下merge k sorted arrays

其他题

Intersection of Two Linked Lists

寻找两个链表的交叉点，如下所示，返回节点c1。如果不存在，返回Null

1
2
3
4
5
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
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
private int getLen(ListNode head){
        int length = 0;
        while (head != null){
            ++length;
            head = head.next;
        }
        return length;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int remainA = getLen(headA);
        int remainB = getLen(headB);
        while (remainA > remainB){
            headA = headA.next;
            --remainA;
        }
        while (remainA < remainB){
            headB = headB.next;
            --remainB;
        }
        // 此时remainA == remainB
        while (headA != null && headB != null && headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        if(headA == headB) return headA;
        else return null;
    }