LeetCode Hot 100 (7) 链表 (一)
# 160. 相交链表 (opens new window)
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
- intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
- skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点(A 中第二个节点和 B 中第三个节点) 是不同的节点。
换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
2
3
4
5
6
7
示例 2:
输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
2
3
4
5
示例 3:
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。
2
3
4
5
提示:
- listA 中节点数目为 m
- listB 中节点数目为 n
- 1 <= m, n <= 3 * 10^4
- 1 <= Node.val <= 10^5
- 0 <= skipA <= m
- 0 <= skipB <= n
- 如果 listA 和 listB 没有交点,intersectVal 为 0
- 如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]
进阶:你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案?
思路:
先计数两个链表的节点数,然后让长的链表先从链表头往下遍历,然后判断两个链表节点是否相同。
代码:
C++代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int sum1 = 0;
ListNode* t1 = headA;
while(t1) {
sum1++;
t1 = t1->next;
}
int sum2 = 0;
ListNode* t2 = headB;
while(t2) {
sum2++;
t2 = t2->next;
}
int k = 0;
if(sum1>sum2) {
k = sum1-sum2;
while(k--) {
headA = headA->next;
}
} else {
k = sum2-sum1;
while(k--) {
headB = headB->next;
}
}
while(headA!=headB) {
headA = headA -> next;
headB = headB -> next;
}
return headA;
}
};
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
Go代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
sum1 := 0
t1 := new(ListNode)
t1 = headA
for t1!=nil {
sum1++
t1 = t1.Next
}
sum2 := 0
t2 := new(ListNode)
t2 = headB
for t2!=nil {
sum2++
t2 = t2.Next
}
k := 0
if sum1>sum2 {
k = sum1 - sum2
for k>0 {
k--
headA = headA.Next
}
} else {
k = sum2 - sum1
for k>0 {
k--
headB = headB.Next
}
}
for headA!=headB {
headA = headA.Next
headB = headB.Next
}
return headA
}
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
# 206. 反转链表 (opens new window)
题目:
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
2
示例 2:
输入:head = [1,2]
输出:[2,1]
2
示例 3:
输入:head = []
输出:[]
2
提示:
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
思路:
迭代法
递归法
代码:
C++代码 迭代法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr) return nullptr;
ListNode* dummyhead = nullptr;
ListNode* pre = dummyhead;
ListNode* cur = head;
ListNode* temp = cur -> next;
while(cur!=nullptr) {
cur->next = pre;
pre = cur;
cur = temp;
if(temp!=nullptr) temp = temp->next;
}
return pre;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
C++代码 递归法
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur) {
if(cur==nullptr) return pre;
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
return reverse(pre, cur);
}
ListNode* reverseList(ListNode* head) {
return reverse(nullptr,head);
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
Go代码 迭代法
func reverseList(head *ListNode) *ListNode {
pre := new(ListNode)
pre = nil
temp := new(ListNode)
for head!=nil {
temp = head.Next
head.Next = pre
pre = head
head = temp
}
return pre
}
2
3
4
5
6
7
8
9
10
11
12
Go代码 递归法
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
return reverse(nil, head)
}
func reverse(pre *ListNode, cur *ListNode) *ListNode {
if cur==nil {
return pre
}
temp := new(ListNode)
temp = cur.Next
cur.Next = pre
pre = cur
cur = temp
return reverse(pre, cur)
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 234. 回文链表 (opens new window)
题目:
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例 1:
输入:head = [1,2,2,1]
输出:true
2
示例 2:
输入:head = [1,2]
输出:false
2
提示:
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路:
直接看进阶要求的思路,首先通过快慢指针找到第一段的最后一个节点作为中间节点,之后反转后面的链表,再之后同时遍历两个链表根据值是否相同来判断回文
代码:
C++代码
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* firstEnd = getFirstEnd(head);
ListNode* secondStart = firstEnd->next;
ListNode* temp = reverse(secondStart);
while(temp!=nullptr) {
if(head->val!=temp->val) return false;
head = head->next;
temp = temp->next;
}
return true;
}
ListNode* getFirstEnd(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast->next!=nullptr&&fast->next->next!=nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr;
ListNode* temp;
while(head!=nullptr) {
temp = head->next;
head->next = pre;
pre = head;
head = temp;
if(temp!=nullptr) temp = temp->next;
}
return pre;
}
};
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
Go代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
firstEnd := getFirstEnd(head)
secondStart := firstEnd.Next
temp := reverse(secondStart)
for temp!=nil {
if temp.Val != head.Val {
return false
}
temp = temp.Next
head = head.Next
}
return true
}
func getFirstEnd(node *ListNode) *ListNode {
fast := new(ListNode)
fast = node
slow := new(ListNode)
slow = node
for fast.Next!=nil && fast.Next.Next!=nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverse(head *ListNode) *ListNode {
pre := new(ListNode)
pre = nil
temp := new(ListNode)
for head!=nil {
temp = head.Next
head.Next = pre
pre = head
head = temp
if temp!=nil {
temp = temp.Next
}
}
return pre
}
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
# 141. 环形链表 (opens new window)
题目:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
2
3
示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
2
3
示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
2
3
提示:
- 链表中节点的数目范围是 [0, 10^4]
- -10^5 <= Node.val <= 10^5
- pos 为 -1 或者链表中的一个有效索引 。
进阶:你能用 O(1)(即,常量)内存解决此问题吗?
思路:
遍历过的节点将其值修改为超过它本身范围的值,然后遍历
代码:
C++代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
while(head!=NULL && head->val!=INT_MAX) {
head->val = INT_MAX;
head = head->next;
}
if(head==NULL) return false;
return true;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Go代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
for head!=nil && head.Val!=math.MaxInt32 {
head.Val = math.MaxInt32
head = head.Next
}
if head==nil {
return false
} else {
return true
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 142. 环形链表 II (opens new window)
题目:
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
2
3
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
2
3
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
2
3
提示:
- 链表中节点的数目范围在范围 [0, 10^4] 内
- -10^5 <= Node.val <= 10^5
- pos 的值为 -1 或者链表中的一个有效索引
进阶:你是否可以使用 O(1) 空间解决此题?
思路:
快慢指针,当两者在环上相遇时,f = 2s,快指针比慢指针多走了n个环的长度,f = s + nb。所以s = nb, f = 2nb。所以当两者相遇时满指针已经走了nb步,由于所有走到环入口节点需要a + kb步,所以再走a步必然能到入口节点。
代码:
C++代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while(fast!=NULL&&fast->next!=NULL) {
slow = slow->next;
fast = fast->next->next;
if(slow==fast) {
ListNode* cur1 = fast;
ListNode* cur2 = head;
while(cur1!=cur2) {
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
}
return NULL;
}
};
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
Go代码
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
fast := new(ListNode)
fast = head
slow := new(ListNode)
slow = head
for fast!=nil && fast.Next!=nil {
slow = slow.Next
fast = fast.Next.Next
if slow==fast {
cur1 := new(ListNode)
cur1 = head
cur2 := new(ListNode)
cur2 = fast
for cur1!=cur2 {
cur1 = cur1.Next
cur2 = cur2.Next
}
return cur1
}
}
return nil
}
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