LeetCode刷题学习-链表篇

数据结构与算法
关于学习
发布日期:   2023-03-01
文章字数:   2k
阅读时长:   9 分
阅读次数:  

链表

移除链表元素

方法一：在原链表的基础上解决，需要对头节点做单独的处理

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* temp;
    // 头节点单独处理
    while(head != NULL && head->val == val) {
        temp = head;
        head = head->next;
        free(temp);
    }

    // 中间节点的处理
    struct ListNode* currentNode = head;
    struct ListNode* prev = NULL;
    while(currentNode != NULL) {
        if(currentNode->val == val) {
            prev->next = currentNode->next;
            struct ListNode* deleteNode = currentNode;
            currentNode = currentNode->next;
            free(deleteNode);
        } else {
            prev = currentNode;
            currentNode = currentNode->next;
        }
    }
    
    return head;
}

方法二：创建一个虚拟头节点，这样所有节点的处理都可以像中间节点一样，而无需对头节点进行单独的处理了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    // 起别名
    typedef struct ListNode ListNode;
    // 建立虚拟头节点
    ListNode* tempHead = (ListNode*) malloc(sizeof(ListNode));
    tempHead->next = head;
    // 遍历指针
    struct ListNode* cur = tempHead;
    
    // 像处理中间节点一样，统一操作
    while(cur->next) { 
        if(cur->next->val == val) {
            struct ListNode* temp = cur->next;
            cur->next = cur->next->next;
            free(temp);
        } else {
            cur = cur->next;
        }
    }
    // 最后记得返回真正的头节点
    head = tempHead->next;
    return head;
}

设计链表

需要注意的是 index 是从0开始的

typedef struct MyLinkedList{
    int val;
    struct MyLinkedList* next;
} MyLinkedList;

// 题中给出的是虚拟头节点的解法，会简单很多
MyLinkedList* myLinkedListCreate() {
    MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    head->next = NULL;
    return head;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    if(obj == NULL) {
        return -1;
    }
    int count = -1;
    while(obj->next) {
        obj = obj->next;
        count++;
        if(count == index) {
            return obj->val;
        }
    }
    return -1;
}

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

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    while(obj->next) {
        obj = obj->next;
    }
    MyLinkedList* newNode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newNode->val = val;
    obj->next = newNode;
    newNode->next = NULL;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    int count = -1;
    MyLinkedList* newNode = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    newNode->val = val;
    // 头插
    if(index < 0) {
        newNode->next = obj->next;
        obj->next = newNode;
        return;
    }
    // 中间正常位置插入
    while(obj->next) {
        MyLinkedList* prev = obj;
        obj = obj->next;
        count++;
        if(count == index) {
            newNode->next = obj;
            prev->next = newNode;
            return;
        }
    }
    // 尾插
    if(obj->next == NULL && count+1 == index) {
        obj->next = newNode;
        newNode->next = NULL;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index < 0) {
        return;
    }
    int count = -1;
    while(obj->next) {
        MyLinkedList* prev = obj;
        obj = obj->next;
        count++;
        if(count == index) {
            MyLinkedList* temp = obj;
            prev->next = obj->next;
            free(temp);
            return;
        }
    }
}

void myLinkedListFree(MyLinkedList* obj) {
    while(obj) {
        MyLinkedList* prev = obj;
        obj = obj->next;
        free(prev);
    }
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/

反转链表

和数组反转类似，都可以利用双指针法（需要注意的细节是原头节点反转后变尾节点，其next需要指向NULL）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev = NULL; 
    // 临时保存
    struct ListNode* temp;
    struct ListNode* cur = head;
    while(cur) {
        // 保存好方便更新cur
        temp = cur->next;
        // 开始反转
        cur->next = prev;
        // 更新指针
        prev = cur;
        cur = temp;
    }
    return prev;
}

两两交换链表中的节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* swapPairs(struct ListNode* head){
    typedef struct ListNode ListNode;
    if(head == NULL) {
        return head;
    }
    // 虚拟头节点
    ListNode* tempNode = (ListNode*)malloc(sizeof(ListNode));
    tempNode->next = head;

    struct ListNode* first = tempNode;
    struct ListNode* second, * third;
    
    while(first && first->next && first->next->next) {
        second = first->next;
        third = first->next->next;
        // 开始交换
        first->next = third;
        second->next = third->next;
        third->next = second;
        // 向后移动
        first = first->next->next;
    }
    return tempNode->next;
}

删除链表的倒数第几个结点

方法一：将倒数转成顺数。先遍历一次链表找到链表的长度 len，然后可以发现，倒数第 n 个恰好是顺数的 len - n + 1 个，然后再遍历执行删除操作即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    typedef struct ListNode ListNode;
    ListNode* tempHead = (ListNode*)malloc(sizeof(ListNode));
    tempHead->next = head;
    int len = 0;
    ListNode* cur = tempHead;
    while(cur->next) {
        cur = cur->next;
        len++;
    }
    cur = tempHead;
    int index = len - n + 1;
    int count = 0;
    ListNode* prev;
    while(cur->next) {
        prev = cur;
        cur = cur->next;
        count++;
        if(count == index) {
            prev->next = cur->next;
            free(cur);
            break;
        }
    }
    return tempHead->next;
}

方法二：（一次遍历完成所有操作）双指针操作。定义fast和slow指针，让 fast 指针先走，当 fast 指向与 slow 指向中间相隔 n 个节点时，两指针再同时移动，直到 fast 指针指向 NULL 时，此时 slow 指针指向的下一个节点即需要删除的节点

image-20230228155804627

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    typedef struct ListNode ListNode;
    ListNode* tempHead = (ListNode*)malloc(sizeof(ListNode));
    tempHead->next = head;
    
    ListNode* fast = head;
    ListNode* slow = tempHead;
    // 先让快指针走，等中间相隔 n 个元素后，快慢指针同时走
    while(n-- && fast != NULL) {
        fast = fast->next;
    }
    while(fast) {
        slow = slow->next;
        fast = fast->next;
    }
    // 快指针指向为 NULL 的时候， 慢指针指向的下一个节点就是需要删除的节点
    ListNode* temp = slow->next;
    slow->next = slow->next->next;
    free(temp);
    return tempHead->next;
}

链表相交

与某年408的真题相类似，双指针法。关键在于先获取两个链表之间的长度差，然后判断长度，让长的先移动，等到两者在同一起跑线后同时移动，当两指针位置相同的时候，就是交汇点，否则就没有交汇点。

image-20230228200258201

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    typedef struct ListNode ListNode;
    int len_A = 0;
    int len_B = 0;
    // 指向A
    ListNode* p = headA;
    // 指向B
    ListNode* q = headB;
    // 获取 A 长度
    while(p) {
        len_A++;
        p = p->next;
    }
     // 获取 B 长度
    while(q) {
        len_B++;
        q = q->next;
    }
    // 长度差
    int substract = len_A > len_B ? len_A - len_B : len_B - len_A;
    // 更新回来，开始准备工作
    p = headA;
    q = headB;
    
    // 长的先移动
    while(substract-- && p && q) {
        if(len_A > len_B) {
            p = p->next;
        } else if(len_A < len_B){
            q = q->next;
        }
    }
    // 此时同一起跑位置
    while(p && q) {
        if(p == q) {
            return q;
        }
        p = p->next;
        q = q->next;
    }
    return NULL;
}

环形链表II

  1. 先判断是否有环：初始化双指针slow与fast，fast 每次走两步， slow 每次走一步，当 slow == fast 的时候说明有环
  2. 再判断初始环入口：fast 回到头节点重新出发，slow继续在原位置继续出发，当两者再次相遇时就是入口位置

作者：chefyuan，链接：https://leetcode.cn/problems/linked-list-cycle-ii/solution/yi-yan-jiu-kan-dong-de-ti-jie-shuang-zhi-4sag/

图例解释：

上图黄色节点为快慢指针相遇的节点，此时快指针走的距离：a+(b+c)n+b

很容易理解b+c为环的长度，a为直线距离，b为绕了n圈之后又走了一段距离才相遇，所以相遇时走的总路程为a+(b+c)n+b，合并同类项得a+(n+1)b+nc。

慢指针走的距离：a+(b+c)m+b,m代表圈数。

然后我们设快指针得速度是慢指针的2倍,含义为相同时间内，快指针走过的距离是慢指针的2倍。

a+(n+1)b+nc=2[a+(m+1)b+mc]整理得a+b=(n-2m)(b+c)，那么我们可以从这个等式上面发现什么呢？b+c为一圈的长度。也就是说a+b等于n-2m个环的长度。

为了便于理解我们看一种特殊情况，当n-2m等于1，那么a+b=b+c整理得，a=c

此时我们只需重新释放两个指针，一个从head释放，一个从相遇点释放，速度相同，因为a=c，所以他俩必会在环入口处相遇，则求得入口节点索引。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode* slow = head;
    ListNode* fast = head;
    while(1) {
        // 无环
        if(fast == NULL || fast->next == NULL) return NULL;
        fast = fast->next->next;
        slow = slow->next;
        // 说明有环
        if(slow == fast) {
            break;
        }
    }
    // fast 重新出发， slow 继续在原位置上出发，当两者再次相遇时，其位置就是入口
    fast = head;
    while(fast != slow) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
数据结构与算法
赏
评论
  目录