[数据结构与算法]LeetCode剑指 Offer——链表中等题的思路和代码

LeetCode剑指 Offer——链表的中等题

1. 剑指 Offer 35. 复杂链表的复制

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

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

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

相关标签：链表 哈希表

解：

1. 如果是普通链表（没有random指针）那就是构造节点再指向，比较简单，但是这个题每个节点多了随机random指针
2. 又不能在构造节点的时候给它指向，因为后面的节点还没造出来，没法指向
3. 主要就是在根据源节点构造一个新的节点时，要知道源节点的指向，而且它们是一一对应的关系，所以这里要使用到哈希映射（HashMap）来存储这种关系

代码（Java）：

class Solution {
    public Node copyRandomList(Node head) {
        Node p = head;
        HashMap<Node,Node> map = new HashMap<>();
        while(p!=null){
            Node pNew = new Node(p.val);//迭代原链表，构造新节点
            map.put(p,pNew);//将源节点和新节点作为键值对存入到哈希表中
            p = p.next;
        }

        p = head;
        while(p!=null){
            map.get(p).next = map.get(p.next);
            //根据键获取对应的值，给值对应的节点的next和random进行指向，它们指向键对应节点的next、random域对应的值
            map.get(p).random = map.get(p.random);
            p = p.next;
        }

        return map.get(head);//最后返回的是头结点对应的值节点
    }
}

2. 剑指 Offer II 026. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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

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

相关标签：链表 双指针

解：

这个题主要涉及到了链表节点位置的一个变化，而且提到了下标——>可以联想到数组，数组使用下标存取很方便，而我们可以把链表的每一个节点存储到数组中，从而实现对节点的存取

观察链表每个节点的指向，可以发现：将最后一个节点放到了第一个节点的后面，倒数第二个节点放在了第二个节点后面。。。

于是可以看出：从头开始，两个节点为一组，这一组节点的下标之和为n

看下图：节点5放到了节点1后，节点4放到了节点2后，所以修改后的指向如图

还要判断一下，中间的节点指向NULL

但是这只是修改了左半部分节点的指向，右半部分节点的指向同理也要修改

对于右半部分来说，由于第一个已经指向了，将除去第一个节点两个为一组，最后一个指向第一个，所以5指向2,4指向3

代码：

void reorderList(struct ListNode* head){

    struct ListNode* p = head; 
    int len = 0;
    while(p){
        len++;
        p = p->next;
    }
    struct ListNode* pArr[len+1] ; //定义数组时使用静态分配内存，不要malloc。这里定义一个结构数组，长度为len+1

    p = head;
    int cur = 0;
    while(cur<=len-1){  //迭代把每个节点放到了数组中
        pArr[cur] = p;
        cur++;
        p = p->next;
    }

    //现在链表就被存储到了数组中，可以使用下标进行访问
    int i = 0,j = len - 1;
    for(i,j;i<=j;i++,j--){  //从第一个节点开始，每个节点指向它对称的那个节点。如果是奇数个节点，最后中间的指向空
        //修改节点的指向
        //规律是：每两个节点一组，下标和为n。对称的两个节点
        pArr[i]->next = pArr[j];	//左半部分节点的指向
        if(i == j)
            pArr[i]->next = NULL;
    }


//第一个已经指向了，从第2个节点开始，修改后半部分节点的指向。每个节点指向它对称的那个节点。
//如果刨去第一个节点后是奇数个节点，最后中间的指向空
    for(i = 1,j = len-1;i<=j;i++,j--){
        pArr[j]->next = pArr[i];	//右半部分节点的指向
        if(i == j)
            pArr[i]->next = NULL;	//同理，这里也要判断
    }
    // printf("%d",pArr[0]->val);
}

3. 剑指 Offer II 021. 删除链表的倒数第 n 个结点

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

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

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

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

相关标签：链表 双指针

解1 ：

倒数第n个节点，可以根据长度求出这是正数第几个节点，再使用链表节点的删除

解2：

使用双指针

本题的双指针规则：

• 快指针从正数第n个节点出发，一次一走一步
• 慢指针从头出发，一次走一步
• 当快指针走到末尾时，慢指针恰好走到倒数第n个节点

除了快慢指针外，还需要定义一个指针，它指向待删除节点的前一个节点，保存它是为了删除操作
（需要注意的是，头结点保存了数据但它没有前驱结点，需要特殊考虑，也可以在头结点前构造一个哑结点避免对头结点的特殊考虑）

1. 定义fast、low均指向head
2. 先让fast迭代到第n个节点的位置
3. 一起迭代，但是迭代时，需要注意如果fast->next->next == NULL时，low此时就指向待删除的前一个节点，需要定义一个节点来保存这个位置。
4. 迭代结束，删除low后面这个位置的节点（注意如果删的是头结点，那么这个p定义之后值没有变，因为删除第一个根本就没有进循环）

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    if(head->next==NULL)//只有一个节点返回空就行
        return NULL;
        
    struct ListNode* high = head,*low = head;
    struct ListNode* p = NULL;  //保存的是待删除节点的前一个节点
    int cur = 1;
    while(cur!=n){//循环结束后，快指针指向第n个节点，这样当快指针走到最后时，慢指针恰好走到倒数第n个
        high = high->next;
        cur++;
    }
    
    while(high->next!=NULL){
        if(high->next->next==NULL){ //满足此条件时，low的指向恰好就是待删除节点的前一个节点
             p = low;
        }
        high = high->next;
        low = low ->next;
    }
   
    // if(n==1)    p->next = NULL;//特殊处理：删除的是最后一个节点
    //这个也不用特殊处理，n=1时 p->next->next就是NULL，知道就行了

     if(p == NULL){//没有经过循环，也是特殊情况，删除的是第一个节点
        return head->next;
    }
    else    p->next = p->next->next;//正常删除
    // free(low);
    return head;

    //由于要找前驱节点，而头结点也有数据，找不到它的前驱节点
    //所以往往可以在它的前面构造一个哑结点指向头结点，便于操作，找到头结点，可以避免对头结点的特殊处理
    struct ListNode* pYa = (struct ListNode*)malloc(sizeof(struct ListNode));
    pYa->next = head;

    //也可以不使用双指针，倒数第n个，就是正数第len-n+1个，添加哑结点，迭代找到前一个节点再删除
}

4. 剑指 Offer II 022. 链表中环的入口节点

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

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

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

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

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

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

相关标签：链表 哈希表 双指针

解：

判断有没有环：

• 可以使用双指针，同一点出发，快指针一次走两步、慢指针一次走一步，如果有环，fast早晚能追杀slow，没环一定追不上（下一次相遇）
• 还可以用HashSet，里面存储节点，由于HashSet不能存储重复元素，所以可用来判断有无环（set.contains()方法）

使用集合的代码（Java）

public class Solution {
    public ListNode detectCycle(ListNode head) {
    // HashSet set = new HashSet();		//链表节点的值可能会重复,所以存储节点，不能存储节点的val
    ListNode fast = head;
    HashSet<ListNode> set = new HashSet<>();
    while(!set.contains(fast)){  	//每次往set中添加节点时，都进行判断集合中有没有这个节点（是否重复）
        if(fast==null)	//如果添加了一个null，说明没有环，直接返回null就可以了
            return null;
        set.add(fast);
        fast = fast.next;
    }
    return fast;	//入环节点就是此时的fast
    }

也可以使用双指针，但是数学运算过程比较复杂

官方：
如下图所示，设链表中环外部分的长度为 aa。\textit{slow}slow 指针进入环后，又走了 bb 的距离与 fast 相遇。此时，fast 指针已经走完了环的 nn 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有

a+(n+1)b+nc=2(a+b)
? a=c+(n?1)(b+c)

有了 a=c+(n-1)(b+c) 的等量关系，我们会发现：从 相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL) {
        slow = slow->next;
        if (fast->next == NULL) {
            return NULL;
        }
        fast = fast->next->next;
        
        if (fast == slow) { //此时相遇
            struct ListNode* ptr = head; //相遇的时候，让一个新指针从头开始去追slow，根据这个公式，追上的时候新指针的位置就是入口
            // 从 相遇点到入环点的距离加上 n-1 圈的环长 = 从链表头部到入环点的距离
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return NULL;
}

5. 剑指 Offer II 025. 链表中的两数相加

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

输入：l1 = [0], l2 = [0]
输出：[0]

相关标签：链表 栈 数学

解：
（一开始做了好长时间，最后还是有个小bug就是最后一个的进位，参考其他人的解答）

• 由于链表的节点相加，需要尾对齐进行加法运算，所以这里需要先对链表进行反转，以方便从头开始进行加法。
• 过程中还可能产生进位，需要有一个变量保存进位，初始值=1
• 反转之后从头开始，但两个链表长度不一定相同，这里最好是以长的为准，然后将短的链表空的那些数据域设为0比较方便
• 求出对应位相加的和，但是要%10，同时保存进位
• 每一次都要构造一个新节点，让新链表头指针指向新节点（在外面定义新链表），指针再后移一位便于下次指向
• 注意的是，最后一次如果有进位，可是迭代已经结束（这个进位没地方加），需要特殊处理，数据域设为1，单独处理

代码：

struct ListNode* reverseList(struct ListNode* head);
struct ListNode* addList(struct ListNode* l1,struct ListNode* l2);
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    struct ListNode* ret = addList(l1,l2);
    return reverseList(ret);
}

struct ListNode* addList(struct ListNode* l1,struct ListNode* l2)
{
    struct ListNode* ret = (struct ListNode*)malloc(sizeof(struct ListNode));  //定义新链表的指针
    ret->val = 0;
    struct ListNode* p = ret;
    int flag = 0;
    while(l1 != NULL || l2 != NULL)  //以长的为准
    {
        int l1_val = l1 != NULL ? l1->val : 0;//把短的链表缺的节点的数据域设为0，方便加
        int l2_val = l2 != NULL ? l2->val : 0;
        int sum = l1_val + l2_val + flag;
        if(sum>=10)
        {
            flag = 1;
            sum -= 10;
        }
        else
            flag = 0;
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = sum;  //定义新节点，再让新链表头指针指向新节点，头指针再后移
        p->next = newNode;
        p = p->next;
        l1 = l1 == NULL ? NULL : l1->next;
        l2 = l2 == NULL ? NULL : l2->next;
    }
    if(flag == 1)	//记录的是最后一位加，产生了进位，这个进位需要单独处理，数据域为1
    {
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = 1;
        p->next = newNode;
        p = p->next;
    }
    p->next = NULL;
    return ret->next;//头结点没有存值，没有实际意义
}
struct ListNode* reverseList(struct ListNode* head){//反转链表
    struct ListNode* front = NULL;
    struct ListNode* mid = head;
    while(mid != NULL)
    {
        struct ListNode* end = mid->next;
        mid->next = front;
        front = mid;
        mid = end;
    }
    return front;
}