「算法刷题」链表的相交、合并的LeetCode题目实现

[TOC]

​ 本文主要记录链表的相交、合并、排序的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、链表相交的LeetCode题目

1、找到2个单链表的相交点

160. 相交链表（简单难度）

面试题 02.07. 链表相交（简单难度）

剑指 Offer 52. 两个链表的第一个公共节点（简单难度）

剑指 Offer II 023. 两个链表的第一个重合节点（简单难度）

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *pA=headA;
        ListNode *pB=headB;
        // 获取两个单链表的长度
        int lenA=0;
        int lenB=0;
        while(pA){
            lenA++;
            pA=pA->next;
        }
        while(pB){
            lenB++;
            pB=pB->next;
        }
        // 让长链表的遍历指针先走
        pA=headA;
        pB=headB;
        if(lenA>lenB){
            int gap=lenA-lenB;
            while(gap--){
                pA=pA->next;
            }
        }
        else if(lenA<lenB){
            int gap=lenB-lenA;
            while(gap--){
                pB=pB->next;
            }
        }
        //长短链表同时开始走
        while(pA&&pB){
            if(pA==pB) return pA;
            pA=pA->next;
            pB=pB->next;
        }
        return NULL;
    }
};

2、环形链表

876. 链表的中间结点（简单难度）

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        // 方法一：快慢指针
        // ListNode* slow=head;
        // ListNode* fast=head;
        // while(slow&&fast&&fast->next){
        //     slow=slow->next;//2,3,4
        //     fast=fast->next->next;//3,5,null
        // }
        // return slow;
        // 方法二：计数法
        int len=0;
        ListNode* p=head;
        if(p==nullptr) return nullptr;
        while(p){
            p=p->next;
            len++;
        }
        // 
        int i=0;
        p=head;
        while(p&&i<len/2){
            p=p->next;
            i++;
        }
        return p;
    }
};

141. 环形链表（简单难度）

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 快慢指针
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast  && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast) return true; //指针相同说明相遇
        }
        return false;
    }
};

142. 环形链表 II（中等难度）

剑指 Offer II 022. 链表中环的入口节点（中等难度）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        // 快指针每次走2步，慢指针每次走1步，相遇即有环
        while(fast  && fast->next ) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，说明有环
            if (slow == fast) {
                slow=head;
                // head和相遇点相同速度出发再次相遇的就是入口
                while(fast&& slow) {
                    // 快慢指针第一次相遇，说明此时为入口
                    if (slow == fast) return slow;;
                    slow = slow->next;
                    fast = fast->next;
                }
            }
        }
        return NULL;
    }
};

二、链表合并的LeetCode题目

1、合并有序链表

21. 合并两个有序链表（简单难度）

剑指 Offer 25. 合并两个排序的链表（简单难度）

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* result = new ListNode(-1); // 结果链表,默认第一个为虚拟头结点
        ListNode* p = result;// 遍历指针，该指针会变化
        // 同时遍历两2个链表
        while(list1&&list2){
            // 谁小将谁添加进结果链表
            if(list1->val<=list2->val){
                p->next=list1;
                list1=list1->next;
            }
            else{
                p->next=list2;
                list2=list2->next;
            }
            p=p->next;
        }
        // 此时有个链表有剩余，继续添加
        while(list1!=NULL){
            p->next=list1;
            list1=list1->next;
            p=p->next;
        }
        while(list2!=NULL){
            p->next=list2;
            list2=list2->next;
            p=p->next;
        }
        return result->next;
    }
};

2、拼接链表

1669. 合并两个链表（中等难度）

class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        // 找到list1的第a-1个节点
        int i=0;
        ListNode* pa=list1;
        while(pa&&i<a-1){
            pa=pa->next;
            i++;
        }
        // 找到list1的第b个节点;
        i=0;
        ListNode* pb=list1;
        while(pb&&i<b){
            pb=pb->next;
            i++;
        }
        // 找到list2的最后一个节点
        ListNode* last=list2;
        while(last->next){
            last=last->next;
        }
        // 拼接两个链表
        pa->next=list2;
        last->next=pb->next;
        return list1;
    }
};