甲乙小朋友的房子

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

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→LnL1→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;
}