【LeetCode】剑指Offer——链表

6 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

题解

/*递归*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if (!head)
            return {};
        vector<int> arr = reversePrint(head->next);
        arr.push_back(head->val);
        return arr;
    }
};

class Solution {
public:
    vector<int> arr;
    vector<int> reversePrint(ListNode* head) {
        if (head)
        {    
            if(head->next)
                reversePrint(head->next);
            arr.push_back(head->val);
        }
        return arr;
    }
};

18 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 $free$ 或 $delete$ 被删除的节点

题解

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

（83） 删除排序链表中的重复元素

给定一个已排序的链表的头 $head$ ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 $[0, 300]$ 内
• $-100 <= Node.val <= 100$
• 题目数据保证链表已经按升序 排列

题解

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head){
            return head;
        }

        ListNode* cur = head;
        while(cur->next){
            if(cur->val == cur->next->val){
                cur->next = cur->next->next;
            }else{
                cur=cur->next;
            }
        }
        return head;
    }
};

（82）删除排序链表中的重复元素 II

给定一个已排序的链表的头 $head$ ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 $[0, 300]$ 内
• $-100 <= Node.val <= 100$
• 题目数据保证链表已经按升序 排列

题解

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head||!head->next)return head;
        ListNode *preHead=new ListNode(0);
        preHead->next=head;
        ListNode *pre=preHead;
        ListNode *cur=head;
        while(cur)
        {
            while(cur->next && cur->val==cur->next->val)
            {
                cur=cur->next;//跳过当前重复节点
            }
            if(pre->next==cur)
            {
                pre=pre->next;//pre无重复节点，pre后移
            }
            else
            {//pre不移动，指向已经遍历完的链表结尾
                pre->next=cur->next;
            }
            cur = cur->next;
        }
        return preHead->next;
    }
};

22 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 $6$ 个节点，从头节点开始，它们的值依次是 $1、2、3、4、5、6$。这个链表的倒数第 $3$ 个节点是值为 $4$ 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* cur = head, *pre=head;

        for(int i=0;i<k;i++)
        {
            cur= cur->next;
        }

        while(cur!=NULL)
        {
            pre=pre->next;
            cur=cur->next;
        }
        return pre;
    }
};

Z22（142） 链表中环的入口节点

定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 $next$ 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 $null$。

为了表示给定链表中的环，我们使用整数 $pos$ 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 $pos$ 是 $-1$，则在该链表中没有环。注意，$pos$ 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 $[0, 104]$ 内
• $-105 <= Node.val <= 105$
• $pos$ 的值为 $-1$ 或者链表中的一个有效索引

进阶：是否可以使用 $O(1)$ 空间解决此题？

题解

/*
 * @lc app=leetcode.cn id=142 lang=cpp
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * 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 *fast = head, *slow = head;
        while(true)
        {
            if(fast == NULL || fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow)break;
        }
        fast = head;
        while(slow != fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};
// @lc code=end

24 环形链表

给你单链表的头节点 $head$ ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 $[0, 5000]$
• $-5000 <= Node.val <= 5000$

题解

/*递归*/
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre){
        if(cur==nullptr)return pre;//终止条件
        ListNode* res = recur(cur->next, cur);//后继节点递归
        cur->next = pre;//修改节点引用指向
        return res;//返回反转链表的头节点
    }

};

/*双指针迭代*/
/**
 * 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 = head, *pre = NULL;
        while(cur!=NULL){
            ListNode* tmp = cur->next; //暂存后继节点cur.next
            cur->next = pre; //修改next引用指向
            pre = cur;//pre暂存cur
            cur = tmp;//cur访问下一节点
        }
        return pre;
    }
};

25（21） 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

题解

/*递归025*/
/**
 * 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==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;
        }
    }
};

/*伪头节点021*/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dum =new ListNode(0), *cur = dum;
        while(list1 != NULL && list2 != NULL)
        {
            if(list1->val < list2->val)
            {
                cur->next = list1;
                list1 = list1->next;
            }
            else
            {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 != NULL ? list1 : list2;
        return dum->next;
    }
};

35（138） 复杂链表的复制

请实现 $copyRandomList$ 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 $next$ 指针指向下一个节点，还有一个 $random$ 指针指向链表中的任意节点或者 $null$。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

• $-10000 <= Node.val <= 10000$
• $Node.random$ 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

题解

/*035*/
/*
// 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) {
        if(head==NULL)return NULL;
        Node* cur = head;
        unordered_map<Node*, Node*>map;

        //复制节点（映射）
        while(cur!= NULL)
        {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;

        //构建新链表的next及random指向
        while(cur!=NULL)
        {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }

        return map[head];
    }
};

/*
 * @lc app=leetcode.cn id=138 lang=cpp
 *
 * [138] 复制带随机指针的链表
 */

// @lc code=start
/*
// 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) {
        if(head == nullptr)return nullptr;
        Node* cur= head;
        //复制各自节点，构建拼接链表
        while(cur!=nullptr)
        {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        //构建各自新节点的random指向
        cur = head;
        while(cur!=nullptr)
        {
            if(cur->random != nullptr)
            {
                cur->next->random= cur->random->next;
            }
            cur= cur->next->next;
        }
        //拆分链表
        cur= head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr)
        {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr;
        return res;
    }
};
// @lc code=end

52（160） 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 $null$.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存

题解

/*052*/
/*160*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while(A!=B){
            A = A != NULL ? A->next : headB;
            B = B != NULL ? B->next : headA;
        }
        return A;
    }
};