leetcode链表常见面试算法题

什么叫ARTS?

每周完成一个ARTS:

  1. Algorithm:每周至少做一个 leetcode 的算法题
  2. Review:阅读并点评至少一篇英文技术文章
  3. Tip:学习至少一个技术技巧
  4. Share:分享一篇有观点和思考的技术文章

作者:陈皓
链接:https://www.zhihu.com/question/301150832/answer/529809529
来源:知乎

Delete Node in a Linked List

从节点唯一的单链表中删除一个节点,不用返回任意数值。

1
2
3
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
方法一
  1. 将下一个节点的值复制到当前节点。注意node=node.next不会改变原链表。
  2. 删除下一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode *next=node->next;
*node=*next;
delete next;
}
};

Remove Nth Node From End of List

在一个循环内删掉链表的倒数第几个数。

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
方法一
  1. 先保存好头指针。
  2. 采用双指针进行遍历,第一个指针遍历到第n位后,第二个指针再从头开始遍历。
  3. 第一个指针到达末尾时,第二个指针的位置即是需要删除的位置,head就是头指针?
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* fast=head;
ListNode* slow=head;
while(n--) {
fast=fast->next;
}
if(fast==NULL)
return head->next;
while(fast->next!=NULL) {
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
return head;
}
};

单链表反转

使用递归和迭代两种方法实现。

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
方法一
  1. 迭代法:在首节点前插入头节点0,名字叫pre,另外cur节点指向head,不断的在pre后面插入cur->next,此时cur后移,直到cur为最后一个节点。
  2. 0->1->2->3->4->5->NULL origin
  3. 0->1->3->4->5->NULL 先把cur->next即2取出来,此时cur->next变成3
  4. 0->2->1->3->4->5->NULL 再把取出来的值即2插入到pre后面,注意插入的时候一定要以pre为基准
  5. 0->2->1->4->5->NULL 先把cur->next即3取出来,此时cur->next变成4
  6. 0->3->2->1->4->5->NULL 再把取出来的值即4插入到pre后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = new ListNode(0);
ListNode* cur = head;
pre->next = cur;
while(cur && cur->next) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
tmp->next = pre->next;
pre->next = tmp;
}
return pre->next;
}
};
方法二
  1. 1->2->3->4->5->NULL
  2. 1->NULL 2->3->4->5->NULL
  3. 2->1->NULL 3->4->5->NULL
  4. 3->2->1->NULL 4->5->NULL
  5. 4->3->2->1->NULL 5->NULL
  6. 5->4->3->2->1->NULL
  7. 设置cur为NULL,先将head的next保存为next,将head插入cur头部,并更新cur。
  8. 更新head为next。
  9. 直到head为NULL。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL;
while(head) {
ListNode* next = head->next;
head->next = cur;
cur = head;
head = next;
}
return cur;
}
};
方法三
  1. 递归法。
  2. ⬇️1->2->3->4->5->NULL
  3. ⬇️1 head为1,head->next=2,⬆️5->4->3->2->1->NULL
  4. ⬇️2 head为2,head->next=3,⬆️5->4->3->2->NULL
  5. ⬇️3 head为3,head->next=4,⬆️5->4->3->NULL
  6. ⬇️4 head为4,head->next=5,⬆️5->4->NULL
  7. ⬇️5 head为5,head->next=NULL,⬆️递归开始返回,结果为head即5
  8. 先将问题递给最后的节点。最后的节点依次递回答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next)
return head;
ListNode* node = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return node;
}
};

Merge Two Sorted Lists

合并两个有序节点。

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
方法一
  1. 依次遍历两链表。
  2. 同时比较链表节点的大小,将节点大的插入到新链表中。(相等的情况就不需要考虑了,再比较一次就好了)
  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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l = new ListNode(0);
ListNode* n = l;
while(l1 && l2) {
if(l1->val < l2->val) {
n->next = l1;
l1 = l1->next;
} else {
n->next = l2;
l2 = l2->next;
}
n = n->next;
}
n->next=l1?l1:l2;
return l->next;
}
};
方法二
  1. 递归法?如果是尾递归,答案不需要返回来,不容易堆栈溢出,如果再加一个行参作为答案栈即可使用。
  2. 1->2->4, 1->3->4
  3. 1 ⬇️ 2>-4, 1->3->4
  4. 1->1⬇️ 2->4, 3->4
  5. 1->1->2 ⬇️ 4, 3->4
  6. 1->1->2->3 ⬇️ 4, 4
  7. 1->1->2->3->4 ⬇️ 4
  8. 1->1->2->3->4->4
  9. 还需要向上递归找回头指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1)
return l2;
else if(!l2)
return l1;
if(l1->val<l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l2->next, l1);
return l2;
}
}
};

Palindrome Linked List

判断一个单链表是否为回文链表。

1
2
3
4
Input: 1->2
Output: false
Input: 1->2->2->1
Output: true
方法一
  1. 使用快慢指针,先找到中间的节点。
  2. 再由中间的节点往两边做对比,需要提前做好数据备份,需要判断是奇偶数。
  3. 如果碰到不相等的,则返回false。
  4. 此时间复杂度为O(n)
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
vector<int> back;
while(fast && fast->next) {
back.push_back(slow->val);
slow = slow->next;
fast = fast->next->next;
}
if(fast && !fast->next) {
slow = slow->next;
}
int i=0;
while(back.size()>0 && slow) {
if(back.back()!=slow->val)
return false;
slow = slow->next;
back.pop_back();
}
return true;
}
};
方法二
  1. 使用快慢指针,先找到中间的节点。
  2. 再由中间的节点往两边做对比,需要将后半段进行反转。
  3. 如果碰到不相等的,则返回false。
  4. 此时间复杂度为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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode* head) {
ListNode* cur=NULL;
while(head) {
ListNode* next = head->next;
head->next = cur;
cur = head;
head = next;
}
return cur;
}

bool isPalindrome(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
if(fast && !fast->next) {
slow = slow->next;
}
slow = reverse(slow);
while(slow) {
if(head->val != slow->val)
return false;
head = head->next;
slow = slow->next;
}
return true;
}
};

Linked List Cycle

判断链表中是否存在环。

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

方法一
  1. 采用快慢指针,判断指针是否会相遇,只能通过判断地址是否相等。
  2. 3,3
  3. 3 2,3 0
  4. 3 2 0,3 0 2
  5. 3 2 0 -4,3 0 2 -4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 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) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}
};
方法二
  1. 使用hash set,不断查看之前的set中是否存在相同的节点了,如果存在,证明就是一个环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 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) {
unordered_set<ListNode*> set;
while(head) {
if(set.find(head)!=set.end())
return true;
set.insert(head);
head = head->next;
}
return false;
}
};
nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!