数据结构：链表核心算法与 LeetCode 精选

1. 移除链表元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newHead = NULL, *newTail = NULL;
    ListNode* pcur = head;
    while(pcur != NULL) {
        if(pcur->val != val) {
            if(newHead == NULL) {
                newHead = newTail = pcur;
            } else {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newTail != NULL) {
        newTail->next = NULL;
    }
    return newHead;
}

2. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

3. 链表的中间节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

4. 返回倒数第 k 个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
int kthToLast(struct ListNode* head, int k) {
    struct ListNode *fast = head, *slow = head;
    while(k--){
        fast = fast->next;
    }
    while(fast != NULL){
        slow = slow->next;
        fast = fast->next;
    }
    return slow->val;
}

5. 合并两个有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL) {
        return list2;
    }
    if(list2 == NULL) {
        return list1;
    }
    struct ListNode* l1 = list1;
    struct ListNode* l2 = list2;
    struct ListNode* newHead, *newTail;
    newHead = newTail = NULL;
    while(l1 && l2) {
        if(l1->val < l2->val) {
            if(newHead == NULL) {
                newHead = newTail = l1;
            } else {
                newTail->next = l1;
                newTail = newTail->next;
            }
            l1 = l1->next;
        } else {
            if(newHead == NULL) {
                newHead = newTail = l2;
            } else {
                newTail->next = l2;
                newTail = newTail->next;
            }
            l2 = l2->next;
        }
    }
    if(l1) {
        newTail->next = l1;
    }
    if(l2) {
        newTail->next = l2;
    }
    return newHead;
}

6. 相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;
    while(curA->next){
        curA = curA->next;
        ++lenA;
    }
    while(curB->next){
        curB = curB->next;
        ++lenB;
    }
    if(curA != curB){
        return NULL;
    }
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA, *shortList = headB;
    if(lenB > lenA){
        longList = headB;
        shortList = headA;
    }
    while(gap--){
        longList = longList->next;
    }
    while(longList != shortList){
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

7. 随机链表的复制

/**
 * Definition for a Node.
 * struct Node {
 * int val;
 * struct Node *next;
 * struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    while(cur){
        struct Node * copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    cur = head;
    while(cur){
        struct Node* copy = cur->next;
        if(cur->random == NULL){
            copy->random = NULL;
        } else{
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    cur = head;
    struct Node* copyHead = NULL,* copyTail =NULL;
    while(cur){
        struct Node* copy = cur->next;
        if(copyTail == NULL) {
            copyHead = copyTail = copy;
        }else {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = copy->next;
    }
    return copyHead;
}