ch2 of programmercarl

C++ C 代码随想录 双指针 链表
刷题
发布日期:   2022-04-17

1 移除链表元素

1.1 题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1:

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

示例2:

输入: head = [], val = 1
输出: []

示例3:

输入: head = [7,7,7,7], val = 7
输出: []

1.2 思路

  由于原链表头可能被移除，因而设置一个哑结点，并将哑结点的 next 指向 head，设置一个prev 指针指向哑结点用于添加新节点，用 cur 指针去遍历原链表，若 cur->val == val 则 cur 后移一位，否则将prev 的 next 指向cur 并将prev 和cur 后移一位。完成原链表遍历后将 prev 的 next 指向 nullptr 以防止原链表中最后的节点的 val 等于待溢出的数值，然后直接返回哑结点的 next 域即可。(C++)

  另一种思路则是用直接先处理链表头出现 val 的节点，如果head->val == val 则将 head 后移一位，然后再用一个 cur 去遍历链表，这里的判断条件改为 cur->next->val==val ，如果成立则将cur 的next 指向 cur->next->next , 注意这里cur 不往后移动，因为下下个节点可能还是等于 val 的，所以还需要对这个节点继续判断；如果不成立，则 cur 后移一位。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new(ListNode);
        dummyHead->next = head;
        ListNode* cur = head, *prev = dummyHead;
        while(cur){
            if(cur->val != val){
                prev->next = cur;
                prev=  prev->next;
            }
            cur = cur->next;
        }
        prev->next =  nullptr;
        return dummyHead->next;
    }
};
  • C 实现
struct ListNode* removeElements(struct ListNode* head, int val){
    while(head && head->val == val){
        head = head->next;
    }
    if(!head){
        return head;
    }
    struct ListNode* cur = head;
    while(cur->next){
        if(cur->next->val==val){
            cur->next = cur->next->next;
        }else{
            cur = cur->next;
        }
    }
    return head;
}

2 设计链表

2.1 题目描述

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • 1addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果 index 小于 0 ，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例1:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

2.2 思路

  创建一个 LinkedList 结构体,然后在 class MyLinkedList 中定义两个 LinkedList 变量,一个为链表头，一个为链表尾；另定义一个 int 变量用于记录当前链表中的节点数。 注意 ，每次进行删除的时候需要判断是否删除的节点是 tail 节点，如果是 tail 节点，那么删除前需要将 tail 往前移动一位，实现方式就是判断 index 是否为 size-1，若是则删除的是 tail 节点， 用 cur 遍历到 tail 节点的前驱节点，然后将 tail 置为 cur， 并将 tail 的 next 置空。

完整代码如下：

  • Cpp 实现
struct LinkedList{
    int val;
    struct LinkedList* next;
};

class MyLinkedList {
public:
    struct LinkedList *head, *tail;
    int size;
    MyLinkedList() {
        head = new(LinkedList);
        tail = head;
        size = 0;
    }
    
    int get(int index) {
        if(index >= size || index < 0){
            return -1;
        }
        struct LinkedList* cur = head->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtTail(int val) {
        struct LinkedList* newNode = new(LinkedList);
        newNode->val = val;
        newNode->next = nullptr;
        tail->next = newNode;
        tail = tail->next;
        ++size;
    }

    void addAtHead(int val) {
        if(size == 0){
            addAtTail(val);
        }else{
            struct LinkedList* newNode = new(LinkedList);
            newNode->val = val;
            newNode->next = head->next;
            head->next = newNode;
            ++size;
        }
    }
    
    void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }else if(index == size){
            addAtTail(val);
        }else if(index <= 0){
            addAtHead(val);
        }else{
            struct LinkedList* cur = head;
            while(index--){
                cur = cur->next;
            }
            struct LinkedList* newNode = new(LinkedList);
            newNode->val = val;
            newNode->next = cur->next;
            cur->next = newNode;
            ++size;
        }
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        struct LinkedList* cur = head;
        if(index == size - 1){
            while(index--){
                cur = cur->next;
            }
            tail = cur;
            cur->next = nullptr;
        }else{
            while(index--){
                cur = cur->next;
            }
            cur->next = cur->next->next;
        }
        --size;
    }
};
  • C 实现
typedef struct MyLinkedList{
    int val;
    struct MyLinkedList *next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList *List = malloc(sizeof(MyLinkedList));
    List->val = 0;          //虚拟结点
    List->next = NULL;      
    return List;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    if(index<0||obj->next==NULL) return -1;

    MyLinkedList *cur = obj->next;
    int order=0;
    while(cur){
        if(cur!=NULL&&order==index){
            break;
        }
        cur=cur->next;
        order++;
    }
    if(order<=order &&cur==NULL){
        return -1;
    }
    return cur->val;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    node->next=NULL;
    if(obj->next ==NULL){
        obj->next = node;
    }else{
        MyLinkedList *next = obj->next;
        obj->next = node;
        node->next =next;
    }
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    node->next=NULL;
    if(obj->next==NULL){
        obj->next = node;
    }else{
        MyLinkedList *cur = obj->next;
        while(cur->next!=NULL){
            cur=cur->next;
        }
        cur->next = node;
    }
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if(index<0) return;

    MyLinkedList *cur = obj->next;
    MyLinkedList *next;
    MyLinkedList *node = (MyLinkedList *)malloc(sizeof(MyLinkedList));
    node->val = val;
    node->next=NULL;

    if(index == 0){
        myLinkedListAddAtHead(obj,val);
    }else{
        int order = 0;
        while(cur!=NULL){
            if(order==index-1) break;
            cur=cur->next;
            order++;
        }
        if(order==index-1&&cur==NULL){
            return;
        }else if(order==index-1&&cur->next!=NULL){
            next = cur->next;
            cur->next = node;
            node->next = next;
        }else if(order==index-1&&cur->next==NULL){
            myLinkedListAddAtTail(obj,val);
        }
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index<0||obj->next==NULL) return;

    if(index==0){
        obj->next=obj->next->next;
    }else{
        MyLinkedList *cur = obj->next;
        int order = 0;
        while(cur){ 
            if(order==index-1) break;
            cur=cur->next;
            order++;
        }
        if(order<=index-1&&cur==NULL){
            return;
        }else if(order==index-1&&cur->next!=NULL){
            cur->next = cur->next->next;
        }
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    MyLinkedList *List = obj->next;
    MyLinkedList *tmp;
    while(List!=NULL){
        tmp = List;
        List = List->next;
        free(tmp);
    }
}

3 反转链表

3.1 题目描述

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

示例1:

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

示例2:

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

示例3:

输入: []
输出: []

3.2 思路

  添加一个虚拟节点 pre 并置为 nullptr ,用 cur 遍历原链表，每次将 cur 的 next 指向 pre, 然后将 cur 和 prev 后移一位。由于 cur 后移前其 next 指向已经改变，即指向了上一个节点，因而我们无法通过 cur->next 来访问原链表中 cur 的下一个节点，因而在修改 cur 的 next 指向前将 cur->next 存起来。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        struct ListNode* pre = nullptr, *cur = head;
        while(cur){
            struct ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
  • C 实现
//递归版
/*struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL||head->next == NULL){
        return head;
    }
    struct ListNode* newHead;
    newHead = reverseList(head->next);  //newHead是最后一层的return，这里赋给倒数第二层的newhead
    head->next->next = head;            //然后倒数第二次return那个newhead，一直循环不变
    head->next = NULL;
    return newHead;         //所以这里return的其实就是最后一层的head
}*/

//迭代版
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    while(cur){
        struct ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

4 两两交换链表中的节点

4.1 题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例1:

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

示例2:

输入: []
输出: []

示例3:

输入: [1]
输出: [1]

4.2 思路

  模拟，第一个节点记为第1个节点，视为奇数节点。用next 存放cur->next->next， 即用next 存放奇数节点，然后将cur->next(cur的下一个偶数节点) 的 next 指向cur (奇偶节点指向反转)，然后将 cur 的 next 指向下下一个偶数节点，即next->next(next为cur后的下一个奇数节点，那么cur后的下下一个偶数节点就是next->next).

  注意，当原链表的节点数为奇数时，已经没有下下个偶数节点了，那就直接将cur 的next 指向下一个奇数节点并完成循环。

整个模拟的过程如下：

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;

        struct ListNode* cur = head;
        head = head->next;
        while(cur && cur->next){
            struct ListNode* next = cur->next->next;
            cur->next->next = cur;
            if(next && next->next){
                cur->next = next->next;
            }else{
                cur->next = next;
            }
            cur = next;
        }
        return head;
    }   
};
  • C 实现
struct ListNode* swapPairs(struct ListNode* head){
    if(head==NULL||head->next==NULL) return head;

    struct ListNode *cur = head,*newHead = cur->next;

    while(cur!=NULL&&cur->next!=NULL){
        struct ListNode *next = cur->next->next;

        cur->next->next = cur;
        if(next!=NULL&&next->next!=NULL){
            cur->next = next->next;
        }else{
            cur->next = next;
        }
        cur = next;
    }
    return newHead;
}

5 删除链表的倒数第 N 个结点

5.1 题目描述

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

示例1:

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

示例2:

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

示例3:

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

5.2 思路

  双指针典型题目。快指针先向后移动 n 步，然后快慢指针同步向后移动，当快指针的 next 指向 nullptr 时，慢指针的 next 恰好指向倒数第 n 个节点，然后直接slow->next = slow->next->next，即将慢指针的 next 指向下下个节点。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head, *slow = head;
        while(fast && fast->next){
            if(n){
                --n;
            }else{
                slow = slow->next;
            }
            fast = fast->next;
        }
        if(n){
            head = head->next;
        }else{
            slow->next = slow->next->next;
        }
        return head;
    }
};
  • C 实现
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    if(head->next == NULL) return NULL;

    struct ListNode *left = head;
    struct ListNode *right = head;
    for(int i=0;i<n;i++){
        right = right->next;
    }
    if(right==NULL){
        return head->next;
    }
    while(right!=NULL&&right->next!=NULL){
        right=right->next;
        left=left->next;
    }
    left->next = left->next->next;
    return head;
}

6 链表相交

6.1 题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例1:

输入: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出: Intersected at ‘8’

示例2:

输入: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出: Intersected at ‘2’

示例3:

输入: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出: null

6.2 思路

  创建两个指针分别遍历两个链表，如果出现 ptr1 == ptr2, 则说明找到交点，而当两个指针指向nullptr, 将其指向另一个链表的表头，如果有交点，那么这样过后就一定会在交点相遇。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *ptrA = headA, *ptrB = headB;
        while(ptrA != ptrB){
            if(!ptrA){
                ptrA = headB;
            }else{
                ptrA = ptrA->next;
            }
            if(!ptrB){
                ptrB = headA;
            }else{
                ptrB = ptrB->next;
            }
        }
        return ptrA;
    }
};
  • C 实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA==NULL||headB==NULL) return NULL;
    struct ListNode* pA =headA;
    struct ListNode* pB =headB;
    while(pA!=pB){
        if(pA==NULL){
            pA = headB;
        }else{
            pA = pA->next;
        }
        if(pB==NULL){
            pB = headA;
        }else{
            pB = pB->next;
        }
    }
    return pA;
}

7 环形链表 II

7.1 题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 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

7.2 思路

  设置两个指针，快指针 fast 每次走两步， 慢指针 slow 每次走一步。

  fast 先进入环，slow 需要走 a 步才到达环的入口，此时 fast 已经走了 2a 步。当 slow 到达环入口，设此时 fast 与 slow 之间的距离为 x.

 fast 什么时候能追上 slow 实现“套圈”呢？由于 fast 与 slow 间的距离每步缩小 1,那么 slow 走 x 步时 fast 就可以追上 slow . 注意：当 slow 到达环入口时两个指针间的距离x 是必定小于环的长度 (可能为 0 ).即慢指针一圈还没走完就会被快指针追上. 设相遇点距离入环点b，则有(设相遇时快指针已经走了 n 圈)

得：

即

  那么想要知道入环点，有一种直接得方法就是让指针自己走到入环点，如何实现？通过上式可以得知，让慢指针走c + (n-1)(b+c), 同时让一个从链表头出发的指针按相同的速度行走，那么必定会在环入口相遇。为什么呢？让慢指针走c + (n-1)(b+c)其实就是走完当前的那一圈，然后再走(n-1)圈，这段距离恰好就是链表头到环入口的距离，所以二者就在环入口相遇。

完整代码如下：

  • Cpp 实现
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return nullptr;
        ListNode* fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if(fast && fast == slow){
                fast = head;
                while(fast!=slow){
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }
        return nullptr;
    }
};
  • C 实现
struct ListNode *detectCycle(struct ListNode *head) {
    if(head==NULL||head->next==NULL) return NULL;
    struct ListNode *fast=head,*slow=head;
    while(1){
        slow=slow->next;
        if(fast==NULL||fast->next==NULL){
            return NULL;
        }
        fast=fast->next->next;
        if(fast==slow){
            struct ListNode *ptr = head;
            while(ptr!=slow){
                slow=slow->next;
                ptr=ptr->next;
            }
            return ptr;
        }
    }
    return NULL;
}

总结

  这一章开始涉及基本的数据结构：链表。

  链表对比数组的优点是：前者的插入和删除的时间复杂度均为O(1)，而后者的时间复杂度为O(n)，因为数组的插入与删除会涉及数组其他元素下标的改变。但是不足之处在于查找某一个元素时需要顺序遍历链表，导致查找的时间复杂度达到O(n).

  链表的基本操作：插入与删除、查找、翻转链表、排序、判断是否成环等，最常用的算法是双指针(即快慢指针)。链表排序本章并未包括，所以有时间自己一定要再做一下那道题！

  链表是最开始刷题的时候做的，截止目前过去半年，基本已经忘光了，所以切记要时常复习数据结构！

文章作者: Vyron Su
文章链接: http://example.com/2022/04/17/ch2-of-programmercarl/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Vyron Su !
C++ C 代码随想录 双指针 链表