Table of Contents
一、题目分类
链表题的分类主要根据算法思想与技巧来分类，产生不同基于链表结构的解题框架。
1.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
|
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p1 = list1, p2 = list2, p = dummy;
while (p1 != null && p2 != null) {
if (p1.val <= p2.val) {
p.next = p1;
p1 = p1.next;
} else {
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if (p1 != null) {
p.next = p1;
}
if (p2 != null) {
p.next = p2;
}
return dummy.next;
}
}
|
递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}
|
1.2 寻找单链表的倒数第 k 个节点
思路框架，双指针的技巧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}
|
单链表的中点：快慢指针
1.3 链表成环
双指针：利用快慢指针，快慢相遇后，继续以慢速度向前+新建一个链表头节点向前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
ListNode meet = null;
while (fast != null) {
if (fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
//到达相遇点
if (fast == slow) {
meet = fast;
while (head != meet) {
head = head.next;
meet = meet.next;
}
return head;
}
}
return null;
}
|
1.4 两个链表是否相交
双指针：到达尾节点则跳到另一个链表的头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while( a != b){
a = a == null? headB : a.next;
b = b == null? headA : b.next;
}
return a;
}
|
1.5 反转链表
迭代方法：用几个变量存链表当前节点、前面节点、后节点即可，一次遍历完成反转。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public ListNode reverseList(ListNode head) {
if (head == null)
return null;
ListNode pre = null;
ListNode next;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
|
递归方法：子问题为链表某节点已经是反转后的链表，返回该头节点
1
2
3
4
5
6
7
8
9
10
11
|
public ListNode reverseList(ListNode head) {
ListNode newHead;
if (head == null || head.next == null) {
return head;
}
newHead = reverseList(head.next); // head.next 作为剩余部分的头指针
// head.next 代表新链表的尾，将它的 next 置为 head，就是将 head 加到末尾了。
head.next.next = head;
head.next = null;
return newHead;
}
|
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
|
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode leftNode = dummy, preE = null, start = null;
for (int i = 0; i < left; i++) {
if (leftNode != null) {
preE = leftNode;
leftNode = leftNode.next;
} else
return head;
}
start = leftNode;
ListNode next = null, pre = null;
int count = right - left;
while (count >= 0 && leftNode != null) {
next = leftNode.next;
leftNode.next = pre;
pre = leftNode;
leftNode = next;
count--;
}
start.next = leftNode;
preE.next = pre;
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
30
31
32
33
34
|
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode p = dummy;
while (p.next != null) {
int len = 0;
ListNode q = p;
while (q.next != null) {
q = q.next;
len++;
if (len == k)
break;
}
if (len != k) {
break;
}
ListNode temp = p.next;
ListNode pre = null, next = null, cur = p.next;
int i = 0;
while (i < k && cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
i++;
}
temp.next = next;
p.next = pre;
p = temp;
}
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
30
31
|
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null)
return true;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
slow = reverseList(slow);
ListNode p1 = head, p2 = slow;
while (p1 != null && p2 != null) {
if (p1.val != p2.val)
return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode pre = null, next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
|