首页 > 代码库 > 算法总结—链表

算法总结—链表

链表题目对算法的要求度不高,但实际写的过程中需要注意语言细节,考虑精细度的地方很多。

1.链表结构与基本操作

1.1 添加节点

一般情况:

cur ->next = prev ->next;
prev ->next = cur;

表头插入:

cur ->next = head;
head = cur;

 

1.2删除节点

一般情况:(已知待删除节点的前驱节点)

ListNode* temp = prev->next;
prev->next = prev->next->next;
delete temp;

表头元素删除:

ListNode* temp = head->next;
delete head;
head = temp;

变形题目:(已知待删除节点,且不知道头指针位置,leetcode237 https://leetcode.com/problems/delete-node-in-a-linked-list/)

思路:将待删除节点后继节点内容拷贝至当前节点,然后删除后继节点,相当于以后继代替当前节点被删除

技术分享
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        ListNode* temp = node->next;
        node->next = node->next->next;
        delete temp;
    }
};
技术分享

注意增删时边界条件的特别处理。

 

2.常见题型总结

2.1Remove Duplicates from Sorted List 1(leetcode83 https://leetcode.com/problems/remove-duplicates-from-sorted-list/)

     Remove Duplicates from Sorted List 2(leetcode82  https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)

 思路:1 直接的思路,即遍历链表,发现相同元素则删除,否则继续下一步

技术分享
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL){
            return head;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        while(head->next != NULL){
            if(head->next->val == head->val){
                ListNode* temp = head->next;
                head->next = head->next->next;
                delete temp;
            }
            else{
                head = head->next;
            }
        }
        return dummy->next;
    }
};
技术分享

2. 因为涉及删除所有重复元素,删除过程需要得到待删除元素的前驱节点,故采用head->next 与 head->next->next比较,保证可以实现删除工作

技术分享
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
    if(head == NULL){
        return head;
    }
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    head = dummy;
    while(head->next != NULL&& head ->next->next != NULL ){
        if(head->next->val == head->next->next->val){
            int val = head->next->val;
            while(head->next != NULL && head->next->val == val){
                ListNode* curr = head->next;
                head->next = head->next->next;
                delete curr;
            }
        }
        else{
            head = head->next;
        }
    }
    return dummy->next;
    }
};
技术分享

 

2.2 链表翻转相关题目

2.2.1 链表整体翻转(Leetcode 206 https://leetcode.com/problems/reverse-linked-list/)

思路:遍历链表,把当前节点作为已经翻转成功链表的新表头(头插法)

技术分享
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* result = NULL;
        while(head){
            ListNode* temp = head->next;
            head ->next = result;
            result = head;
            head = temp;
        }
        return result;
    }
};
技术分享

 

2.2.2 链表部分翻转(Leetcode 92 https://leetcode.com/problems/reverse-linked-list-ii/)

思路:将链表看做三部分,即头到m,m到n,n到最后。

将m,n之间进行翻转后,将链表重新连接,注意处理m为1时的情况(利用dummy node,统一处理)

技术分享
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        for(int i = 0;i < m-1;i++){
            head = head->next;
        }
        ListNode* temp1 = head;
        head = head->next;
        ListNode* temp2 = head;
        ListNode* result = NULL;
        for(int i = m;i <= n; i++){
            ListNode* temp = head->next;
            head->next = result;
            result = head;
            head = temp;
        }
        temp1->next = result;
        temp2->next = head;
        return dummy->next;
    }
};
技术分享

 

2.2.3 链表回文判断(Leetcode 234 https://leetcode.com/problems/palindrome-linked-list/)

思路:找到链表中点(方法见后续 two pointers),将后半部分翻转,与前半部分比较,得到是否回文。

技术分享
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if( head == NULL ||head ->next == NULL ){
            return true;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        while( fast->next != NULL &&  fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
     //   ListNode* mid = slow;
        slow = slow->next;
        ListNode* result = NULL;
        while(slow != NULL){
            ListNode* temp = slow->next;
            slow->next = result;
            result = slow;
            slow = temp;
        }
        //mid->next = NULL;
        while( result != NULL){
            if(head->val != result->val){
                return false;
            }
            head = head->next;
            result = result->next;
        }
        return true;
        
    }
};
技术分享

 

2.3 Two pointers 思路应用

2.3.1  寻找链表中点位置或某一特殊点位置  (Leetcode 19 https://leetcode.com/problems/remove-nth-node-from-end-of-list/) 

思路: 快指针一次走两步,慢指针一次走一步,快指针到达链表末尾时,慢指针指向中点。

技术分享
ListNode* findMiddle(ListNode* head){
        ListNode* chaser = head;
        ListNode* runner = head->next;
        while(runner != NULL && runner->next != NULL){
            chaser = chaser->next;
            runner = runner->next->next;
        }
        return chaser;
    }
技术分享

一个指针先走n步,然后快慢指针一起走,快指针达到末尾时,慢指针达到待删除节点。

注意事项:删除首元素时往往出现问题,可使用dummy node使链表加哨兵,使链表可以统一处理。

技术分享
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head == NULL){
            return head;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        ListNode* slow = head;
        ListNode* fast = head;
        for(int i = 0; i <n; i++){
            fast = fast ->next;
        }
        while(fast->next != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* temp = slow->next;
        slow ->next = slow->next->next;
        delete temp;
        return dummy->next;
    }
};
技术分享

 

2.3.2 给定单链表,找到二者交点(Leetcode 160 https://leetcode.com/problems/intersection-of-two-linked-lists/)

思路:计算链表长度,让较长链表先走差值的距离,后同时遍历,找到相同元素为止

技术分享
class Solution {
public:
    int getLength(ListNode* head){
        int num = 0;
        while(head != NULL){
            head = head->next;
            num++;
        }
        return num;
    }
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lA = getLength(headA);
        int lB = getLength(headB);
        if(lA >= lB){
            for(int i = 0; i < lA - lB; i++){
                headA = headA->next;
            }
        }
        else{
            for(int i = 0;i < lB - lA; i++){
                headB = headB->next;
            }
        }
        while(headA != NULL && headB != NULL){
            if(headA == headB){
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
    }
};
技术分享

 

2.3.3 判断单链表是否有环

(Leetcode 141 142 https://leetcode.com/problems/linked-list-cycle/   https://leetcode.com/problems/linked-list-cycle-ii/)

思路: 1)Two pointers 一快一慢,有环的话,必然相遇。

技术分享
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL){
            return 0;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast!= NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                return 1;
            }
        }
        return 0;
    }
};
技术分享

 

2)  

技术分享

2(a + b) = a + b +n(b + c)

推出 a = (n-1)b + nc 即 a = (n-1)(b+c) + c

因为b+c是环的长度, 所以说讲两个指针分别指链表头和初始相遇位置,他们还会在环开始位置相遇,由此整理思路

① 同第一题,快慢指针判断是否存在环,并记录相遇的位置

② 将两指针分别放置在开头和相遇位置,同样速度推进,则根据推导应该在环开始位置相遇

技术分享
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL){
            return 0;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                break;
            }
        }
        if(fast == NULL || fast->next == NULL){
            return NULL;
        }
        slow = head;
        while(slow != fast){
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};
技术分享

 

待续

算法总结—链表