Day.53———链表常见算法（长期更新）

﹏ヽ暗。殇╰゛Y 2023-03-13 05:22 1阅读 0赞

struct ListNode { 
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) { }
      };

#### 删除某节点 ####

ListNode* deleteNode(ListNode* head, int val) { 
        if(!head) return NULL;
        if(head->val == val) return head->next;
        head->next = deleteNode(head->next, val);
        return head;
    }

#### 删除链表中重复元素 ####

ListNode* deleteDuplicates(ListNode* head) { 
        if(head == NULL || head ->next == NULL) return head;
        while(head->val == head->next->val)
        { 
            head->next = head->next->next;
            if(head->next == NULL) return head;
        }
        head->next = deleteDuplicates(head->next);
        return head;
    }

#### 判断链表是否有“环” ####

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

#### 找到两相交链表的相交点 ####

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 
            if(headA == NULL || headB == NULL) return NULL;
            ListNode *A = headA;
            ListNode *B = headB;
            while(A != B)
            { 
                A= (A==NULL)?  headB:A->next;
                B= (B==NULL)?  headA:B->next;
            }
            return A;
        }

#### 合并两个有序链表 ####

if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1->val <= l2->val) 
            { 
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
        else
            { 
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }

#### 合并K个有序链表 ####

class Solution { 
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) { 
            if(!lists.size()) return NULL;
            return mergeSort(lists, 0, lists.size()-1);
        }
    
        ListNode* mergeSort(vector<ListNode*>& lists, int L, int R) { 
            if (L >= R) return lists[L];
    
            int mid = L + (R-L)/2;
            ListNode* L_list = mergeSort(lists, L, mid);
            ListNode* R_list = mergeSort(lists, mid + 1, R);
            
            return mergeTwoLists(L_list, R_list);
        }
    
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { 
            if(l1 == NULL) return l2;
            if(l2 == NULL) return l1;
            if(l1->val <= l2->val) 
                { 
                    l1->next = mergeTwoLists(l1->next, l2);
                    return l1;
                }
            else
                { 
                    l2->next = mergeTwoLists(l1, l2->next);
                    return l2;
                }
        }
    
    };

#### 将链表逆序 ####

//递归方法
    ListNode* reverseList(ListNode* head) { 
            if (head == NULL || head->next == NULL) return head;
            ListNode* p = reverseList(head->next);
            head->next->next = head;
            head->next = NULL;
            return p;
    }
    
    //非递归方法
    ListNode* reverseList(ListNode* head) { 
            ListNode* prev = NULL;
            ListNode* curr = head;
            while (curr != NULL) { 
                ListNode* nextTemp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
    }

#### 判断链表是否为“回文链表” ####

bool isPalindrome(ListNode* head) { 
            if ( !head ) return true;
            ListNode* fast = head->next, *slow = head;
            while( fast && fast->next ){ 
                fast = fast->next->next;
                slow = slow->next;
            }
            // slow->next是后半段的链表的head
            // 把后半段翻转
            ListNode* pre=NULL, *cur=slow->next, *sav;
            while(cur){ 
                sav = cur->next;
                cur->next = pre;
                pre = cur;
                cur = sav;
            }
            // 翻转结束
            // pre就是翻转后的head
            cur = pre;
            fast = head;
            while(cur&&fast&&cur->val==fast->val){ 
                cur = cur->next;
                fast = fast->next;
            }
            bool res = cur==NULL;
            // 还原链表
            cur = pre;
            pre = NULL;
            while(cur){ 
                sav = cur->next;
                cur->next = pre;
                pre = cur;
                cur = sav;
            }
            slow->next = pre;
            return res;
        }

#### 返回链表倒数第K个元素 ####

ListNode* getKthFromEnd(ListNode* head, int k) { 
            //快慢指针
            ListNode* fast = head;
            ListNode* slow = head;
            while(k--) fast = fast->next;
            while(fast)
            { 
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }