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

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

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. 删除下一个节点。

/**
 * 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

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

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就是头指针？

/**
 * 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;
    }
};

单链表反转

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

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后面

/**
 * 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; // 先把head的下一个位置的值取出来
            cur->next = cur->next->next;
            tmp->next = pre->next; // 插入到pre后面
            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。

/**
 * 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. 先将问题递给最后的节点。最后的节点依次递回答案。

/**
 * 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

合并两个有序节点。

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

方法一

1. 依次遍历两链表。
2. 同时比较链表节点的大小，将节点大的插入到新链表中。（相等的情况就不需要考虑了，再比较一次就好了）
3. 如果一方已经遍历完成，则将剩下的链表直接接入即可。

/**
 * 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. 还需要向上递归找回头指针

/**
 * 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

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

Input: 1->2
Output: false
Input: 1->2->2->1
Output: true

方法一

1. 使用快慢指针，先找到中间的节点。
2. 再由中间的节点往两边做对比，需要提前做好数据备份，需要判断是奇偶数。
3. 如果碰到不相等的，则返回false。
4. 此时间复杂度为O(n)

/**
 * 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)

/**
 * 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

判断链表中是否存在环。

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

/**
 * 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中是否存在相同的节点了，如果存在，证明就是一个环。

/**
 * 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;
    }
};

再定义一个指针指向链表起点，一次走一步，slow 指针也同步继续往后走，那么这两个指针就一定会在链表的入口位置相遇。

if (slow == fast){//快慢指针相遇时
    ListNode ptr = head;//定义一个新指针
    while (ptr != slow){
        ptr = ptr.next;
        slow = slow.next;
    }
    return ptr;//返回环的入口位置
}

k 个一组翻转链表

思路一：

用栈，我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的！
这里要注意几个问题：
第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；
第二，已经翻转的部分要与剩下链表连接起来。

ListNode* reverseKGroup(ListNode* head, int k) {
    stack<ListNode*> st;
    ListNode *dummy = new ListNode(0);
    ListNode *p = dummy;
    while (true) {
        int count = 0;
        ListNode* tmp = head;
        while (tmp != nullptr && count < k) { // 将k个放入栈中
            st.push(tmp);
            tmp = tmp->next;
            count++;
        }
        if (count != k) { // 不够k个不用翻转，直接跳出
            p->next = head;
            break;
        }
        while (!st.empty()) {
            p->next = st.top();
            st.pop();
            p = p->next;
        }
        p->next = tmp;
        head = tmp;
    }
    return dummy->next;
}

思路二：

尾插法。
直接举个例子：k = 3。
pre
tail head
dummy 1 2 3 4 5

我们用tail 移到要翻转的部分最后一个元素

pre head tail
dummy 1 2 3 4 5
cur

我们尾插法的意思就是,依次把cur移到tail后面

pre tail head
dummy 2 3 1 4 5
cur

依次类推

pre tail head
dummy 3 2 1 4 5
cur

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *pre = dummy;
    ListNode *tail = dummy;
    while (true) {
        int count = 0;
        while (tail != nullptr && count != k) {
            count++;
            tail = tail->next;
        }
        if (tail == nullptr) break;
        ListNode *head1 = pre->next;
        while (pre->next != tail) { // 将tail移到要翻转的部分最后一个元素
            ListNode *cur = pre->next; // cur为待移动的元素
            pre->next = cur->next;
            cur->next = tail->next; // 放到tail后面
            tail->next = cur;
        }
        pre = head1;
        tail = head1;
    }
    return dummy->next;
}

递归

将头部的 k 个节点反转，并拼接上后面的第 k + 1 个节点

public ListNode reverseKGroup(ListNode *head, int k) {
    ListNode *newHead = head;
    int count = 0;
    while (newHead != nullptr && count != k) {
        newHead = newHead->next;
        count++;
    }
    if (count == k) { // 找到了k个
        newHead = reverseKGroup(newHead, k); // 将头部的 k 个节点反转，并拼接上后面的第 k + 1 个节点
        // 尾插法
        // head                            newHead
        // 1       2       3       4       5
        // head                    newHead
        // 2       3       4       1       5
        // head            newHead
        // 3       4       2       1       5
        // head
        // newHead
        // 4       3       2       1       5
        while (count != 0) {
            count--;
            ListNode *tmp = head->next;
            head->next = newHead;
            newHead = head;
            head = tmp;
        }
        head = newHead;
    }
    return head;
}

从链表中删去总和值为零的连续节点

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

1   2   -3  3   1
1   3   0   3   4 // sum
    next    next
sum作为key，node作为map保存下来
有两个key=3的，会被后面那个3覆盖，后面map[3]->next才是有效的，本来next指向-3的，改为next指向1，中间的-3 3就被删去了

ListNode* removeZeroSumSublists(ListNode* head) {
    map <int,ListNode*> map;
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    
    int sum = 0;
    //计算各个节点的前缀和存入map，若有相同前缀和会被后面的覆盖
    for (ListNode* d = dummy; d != NULL; d = d->next) {
        sum += d->val;
        map[sum] = d;
    }

    // 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0
    // 直接删除区间所有节点（从前面的一个sum处的节点指向后面的另一个sum处的节点的next）
    sum = 0;
    for (ListNode* d = dummy; d != NULL; d = d->next) {
        sum += d->val;
        d->next = map[sum]->next;
    }

    return dummy->next;
}

链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。

ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode *dummy = new ListNode(0);
    dummy->next = head;
    ListNode *preStart = dummy;
    ListNode *start = head;
    for (int i = 1; i < m; i ++ ) { // 找到m的位置
        preStart = start;
        start = start->next;
    }
    // reverse
    for (int i = 0; i < n - m; i ++ ) { // 头插法反转n次
        ListNode *temp = start->next; // 先保存起来
        start->next = temp->next; // 后面要赋值了
        temp->next = preStart->next; // 后面又要赋值了
        preStart->next = temp; // 最前面链接起来
    }
    return dummy->next;
}