链表

链表

晚风吻尽荷花叶 57 2025-03-02

最近刚学习了链表，顺便做一些练习题以巩固理解，这些题目主要来自leetcode热题100，剑指offer以及牛客算法面试TOP101。

链表这里常见的方法主要有：

1.头插尾插；

2.快慢指针；

注意：下列有的题解为了代码简洁在开辟了头结点后并未释放，这在leetcode这类在线编程平台均可通过，但在真实编程中需特别注意防止内存泄漏。

一.翻转类题目

1.206. 反转链表 - 力扣（LeetCode）

思路1：

        顺序遍历原链表，用原链表每个结点的值构造新结点，依次头插形成新链表。

题解1：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *dummy = new ListNode,*cur = head;
        while(cur)
        {
            ListNode *tmp = new ListNode(cur->val);
            tmp->next = dummy->next;
            dummy->next = tmp;
            cur = cur->next;
        }
        return dummy->next;
    }
};

思路2：

        多指针；

题解2：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head,*pre = nullptr,*next = nullptr;
        while(cur)
        {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

 2.24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：

        递归。

题解：

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
 
        ListNode *tmp = swapPairs(head->next->next);
        ListNode *ret = head->next;
        ret->next = head;
        head->next = tmp;
        return ret;
    }
};

3.25. K 个一组翻转链表 - 力扣（LeetCode）

思路：

头插。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *cur = head;
        int cnt = 0;
        while(cur)
        {
            cur = cur->next;
            cnt++;
        }
        cnt /= k;

        cur = head;
        ListNode *dummy = new ListNode,*pre = dummy;
        for(int i = 0;i < cnt;i++)
        {
            ListNode *tmp = cur;
            for(int j = 0;j < k;j++)
            {
                ListNode *next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
                cur = next;
            }
            pre = tmp;
        }
        pre->next = cur;
        return dummy->next;
    }
};

4.链表内指定区间反转_牛客题霸_牛客网

思路：

模拟；

题解：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy,*cur = head;
        for(int i = 0;i < m - 1;i++)
        {
            cur = cur->next;
            pre = pre->next;
        }
        for(int j = 0;j < n - m;j++)
        {
            ListNode *tmp = cur->next;
            cur->next = tmp->next;
            tmp->next = pre->next;
            pre->next = tmp;
        }
        return dummy->next;
    }
};

二.环类题目

1.141. 环形链表 - 力扣（LeetCode）

思路：

        快慢指针。

题解：

 * 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,*fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};

2.142. 环形链表 II - 力扣（LeetCode）

思路：

        快慢指针。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                slow = head;
                while(slow != fast)
                {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

三.合并类题目

1.21. 合并两个有序链表 - 力扣（LeetCode）

思路：

        尾插。

题解：

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *cur1 = list1,*cur2 = list2,*dummy = new ListNode,*tail = dummy;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                tail = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        tail->next = cur1 == nullptr? cur2 : cur1;
        return dummy->next;
    }
};

2.23. 合并 K 个升序链表 - 力扣（LeetCode）​​​​​​

思路1：

        两两合并。

题解1：

          /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwolists(ListNode* head1,ListNode* head2)
    {
        ListNode *cur1 = head1,*cur2 = head2,*dummy = new ListNode,*tail = dummy;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                tail = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        tail->next = cur1 != nullptr? cur1 : cur2;
        return dummy->next;
    }
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return nullptr;
        if(lists.size() == 1)
            return lists[0];
 
        ListNode *dummy = new ListNode;
        for(int i = 0;i < lists.size() - 1;i++)
        {
            if(i == 0)
            {
                ListNode *tmp = mergeTwolists(lists[0],lists[1]);
                dummy->next = tmp;
            }
            else
            {
                ListNode *tmp = mergeTwolists(dummy->next,lists[i+1]);
                dummy->next = tmp;
            }
        }
        return dummy->next;
    }
};

思路2：

利用优先级队列。

题解2：

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    struct cmp
    { 
        bool operator()(const ListNode* l1,const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> heap;
        for(auto e : lists)
        {
            if(e)
                heap.push(e);
        }
        ListNode *dummy = new ListNode,*tail = dummy;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            tail->next = t;
            tail = t;
            if(t->next)
                heap.push(t->next);
        }
        return dummy->next;
    }
};

四.重排类题目

1.143. 重排链表 - 力扣（LeetCode）

思路：

（1）找中点；

（2）翻转；

（3）合并。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode *head)
    {
        ListNode *dummy = new ListNode,* cur = head;
        while(cur != nullptr)
        {
            ListNode *tmp = new ListNode(cur->val);
            tmp->next = dummy->next;
            dummy->next = tmp;
            cur = cur->next;
        }
        return dummy->next;
    }

    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
            return;

        //1.找到链表的中间位置
        ListNode *dummy = new ListNode,*tail = dummy,*slow = head,*fast = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        //2.逆序链表
        ListNode *cur2 = reverseList(slow->next);
        slow->next = nullptr;
        ListNode *cur1 = head;

        //3.合并cur1和cur2
        while(cur1)
        {
            tail->next = cur1;
            tail = cur1;
            cur1 = cur1->next;
            if(cur2)
            {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        return;
    }
};

2.链表的奇偶重排_牛客题霸_牛客网

思路：

模拟。

题解：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode *odd = head,*even = head->next,*evenHead = head->next;
        while(even != nullptr && even->next != nullptr)
        {
            odd->next = even->next;
            odd = even->next;

            even->next = odd->next;
            even = odd->next;
        }
        odd->next = evenHead;

        return head;
    }
};

五.删除由于链表中的重复元素

1.删除有序链表中重复的元素-I_牛客题霸_牛客网

题解：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *cur = head;
        while(cur != nullptr && cur->next != nullptr)
        {
            if(cur->val == cur->next->val)
                cur->next = cur->next->next;
            else
                cur = cur->next;
        }
        return head;
    }
};

2.删除有序链表中重复的元素-II_牛客题霸_牛客网

题解：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *cur = dummy;
        while(cur->next != nullptr && cur->next->next !=nullptr)
        {
            if(cur->next->val == cur->next->next->val)
            {
                int val = cur->next->val;
                while(cur->next != nullptr && cur->next->val == val)
                    cur->next = cur->next->next;                
            }
            else 
            {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

 六.其他类

1.160. 相交链表 - 力扣（LeetCode）

思路1：

        分别遍历两个链表得出两个链表长度，然后长的链表向后移动长度之差步，接着长短链表同时移动，直到遇到相交结点或者无交点结束。

题解1：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *cur1 = headA,*cur2 = headB;
        int len1 = 0,len2 = 0;
        while(cur1)
        {
            cur1 = cur1->next;
            len1++;
        }
        while(cur2)
        {
            cur2 = cur2->next;
            len2++;
        }
        cur1 = headA;
        cur2 = headB;
        int k = len1 - len2;
        if(len1 >= len2)
        {
            while(k--)
                cur1 = cur1->next;
        }
        else
        {
            k *= -1;
            while(k--)
                cur2 = cur2->next;
        }
        while(cur1 != cur2)
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return cur1;
    }
};

思路2：

        一个链表遍历完之后又从另一个链表头开始出发。

题解2：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *cur1 = headA,*cur2 = headB;
        while(cur1 != cur2)
        {
            cur1 = cur1 != nullptr? cur1->next : headA;
            cur2 = cur2 != nullptr? cur2->next : headB;
        }
        return cur1;
    }
};

2.234. 回文链表 - 力扣（LeetCode）

思路：

        快慢指针找到链表中点，反转后半段链表，比较两个链表查看是否回文。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode *dummy = new ListNode,*cur = head;
        while(cur)
        {
            ListNode *tmp = new ListNode(cur->val);
            tmp->next = dummy->next;
            dummy->next = tmp;
            cur = cur->next;
        }
        return dummy->next;
    }

    bool isPalindrome(ListNode* head) {
        ListNode *slow = head,*fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = head;
        ListNode *tmp = reverseList(slow);
        while(fast && tmp)
        {
            if(fast->val != tmp->val)
                return false;
            fast = fast->next;
            tmp = tmp->next;
        }
        return true;
    }
};

3. 2. 两数相加 - 力扣（LeetCode）

思路：

        各位相加，用和构造新结点，然后尾插形成新链表。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *cur1 = l1,*cur2 = l2,*dummy = new ListNode,*tail = dummy;
        int carry = 0;
        while(cur1 || cur2)
        {
            int val1 = cur1 == nullptr? 0 : cur1->val;
            int val2 = cur2 == nullptr? 0 : cur2->val;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            sum %= 10;
            ListNode *tmp = new ListNode(sum);
            tail->next = tmp;
            tail = tmp;
            if(cur1)
                cur1 = cur1->next;
            if(cur2)
            cur2 = cur2->next;
        }
        if(carry == 1)
            tail->next = new ListNode(1);
        return dummy->next;
    }
};

4. 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：

        找到倒数第N+1个。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow = head,*fast = head;
        n += 1;
        while(n--)
        {
            if(fast == nullptr)
                return head->next;
            fast = fast->next;
        }
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

5. 138. 随机链表的复制 - 力扣（LeetCode）

思路：

        （1）拷贝原结点形成拷贝结点并更改连接关系；

        （2）random指针的处理；

        （3）尾插拷贝结点并恢复原链表；

题解：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
 
class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node *cur = head;
        while(cur)
        {
            Node *copy = new Node(cur->val);
            copy->next = cur->next;
            cur->next = copy;
            cur = cur->next->next;
        }
        cur = head;
        while(cur)
        {
            if(cur->random == nullptr)
            {
                cur->next->random = nullptr;
                cur = cur->next->next;
            }
            else
            {
                cur->next->random = cur->random->next;
                cur = cur->next->next;
            }
        }
        Node *dummy = new Node(0),*tail = dummy;
        cur = head;
        while(cur)
        {
            tail->next = cur->next;
            tail = cur->next;
            cur->next = cur->next->next;
            cur = cur->next;
        }
        return dummy->next;
    }
};

6. 148. 排序链表 - 力扣（LeetCode）

思路：

        遍历，利用排序函数排序,再尾插。

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode *cur = head,*dummy = new ListNode,*tail = dummy;
        vector<int> v;
        while(cur)
        {
            v.push_back(cur->val);
            cur = cur->next;
        }
        sort(v.begin(),v.end());
        for(int i = 0;i < v.size();i++)
        {
            ListNode *tmp = new ListNode(v[i]);
            tail->next = tmp;
            tail = tmp;
        }
        return dummy->next;
    }
};