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
欢迎您扫一扫上面的微信公众号，订阅我的博客！
坚持原创技术分享，您的支持将鼓励我继续创作！