文章

链表题简单题

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针，适合动态插入和删除操作。

发表于 更新于
作者 Sylvan
8 分钟阅读
链表题简单题

链表简单题

面试题 02.03. 删除中间节点

1
2
3
4
5

void deleteNode(struct ListNode *node) {
    // 转换成删除下一个节点
    node->val = node->next->val;
    node->next = node->next->next;
}

1290. 二进制链表转整数

1
2
3
4
5
6
7
8
9
10

int getDecimalValue(struct ListNode *head) {
    struct ListNode *cur = head;
    int res = 0;
    while (cur != NULL) {
        res <<= 1;
        res += cur->val;
        cur = cur->next;
    }
    return res;
}

面试题 02.02. 返回倒数第 k 个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int kthToLast(struct ListNode *head, int k) {
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    // 快指针先走k步
    while (k > 0) {
        fast = fast->next;
        k--;
    }
    // 快慢指针同时走
    while (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

LCR 024. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 迭代
struct ListNode *reverseList(struct ListNode *head) {
    struct ListNode *pre = NULL;
    struct ListNode *next;
    struct ListNode *cur = head;

    // 原地反转
    while (cur != NULL) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

1
2
3
4
5
6
7
8
9
10

// 递归
struct ListNode *reverseList(struct ListNode *head) {
    // 递归出口
    if (head == NULL || head->next == NULL) return head;
    // 递归式
    struct ListNode *newHead = reverseList(head->next); // 递归反转后面的链表
    head->next->next = head; // 下个结点也就是反转后的尾节点，指向自己
    head->next = NULL; // 自己作为新的尾节点
    return newHead;
}

876. 链表的中间结点

1
2
3
4
5
6
7
8
9
10
11

// 返回向上取整的中间节点
struct ListNode *middleNode(struct ListNode *head) {
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    // 慢指针每走一步，快指针走两步
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

LCR 023. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    ListNode* p = headA;
    ListNode* q = headB;
    while (p != nullptr && q != nullptr) {
        p = p->next;
        q = q->next;
    }
    // 先到结尾的是快指针
    ListNode* slow, * fast;
    if (p == nullptr) {
        fast = headA;
        slow = headB;
    } else {
        fast = headB;
        slow = headA;
    }

    // 慢指针先走
    while (p != nullptr) {
        p = p->next;
        slow = slow->next;
    }
    while (q != nullptr) {
        q = q->next;
        slow = slow->next;
    }

    while (slow != nullptr) {
        if (slow == fast) return slow;
        slow = slow->next;
        fast = fast->next;
    }

    return nullptr;
}

面试题 02.01. 移除重复节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 散列
struct ListNode *removeDuplicateNodes(struct ListNode *head) {
    if (head == NULL || head->next == NULL) return head;
    int hash[20001]; // 记录是否出现过
    memset(hash, 0, sizeof(hash));
    struct ListNode *p = head;
    hash[head->val] = 1;

    // 判断当前下个节点是否需要删除
    while (p != NULL && p->next != NULL) {
        if (hash[p->next->val] == 0) {
            // 首次出现
            hash[p->next->val] = 1;
            // 指针后移
            p = p->next;
        } else {
            // 删除已经出现过
            p->next = p->next->next;
            // 指针无需后移
        }
    }
    return head;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// 不用额外空间
// 删除链表中所有值为 k 的节点
struct ListNode *removeNode(struct ListNode *head, int k) {
    struct ListNode *headNode = (struct ListNode *) malloc(sizeof(struct ListNode));
    headNode->next = head;
    struct ListNode *p = headNode;

    while (p != NULL && p->next != NULL) {
        if (p->next->val == k) {
            // 跳过节点
            p->next = p->next->next;
            // 指针无需后移
        } else {
            // 指针后移
            p = p->next;
        }
    }

    return headNode->next;
}

struct ListNode *removeDuplicateNodes(struct ListNode *head) {
    if (head == NULL || head->next == NULL) return head;
    struct ListNode *cur = head;
    while (cur != NULL && cur->next != NULL) {
        // 删除后续链表中和当前值相同的所有节点
        cur->next = removeNode(cur->next, cur->val);
        cur = cur->next;
    }
    return head;
}

21. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 迭代
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* p = list1;
    ListNode* q = list2;
    ListNode* dummy = new ListNode();
    ListNode* cur = dummy;

    while (p != nullptr && q != nullptr) {
        if (p->val <= q->val) {
            cur->next = p;
            p = p->next;
        } else {
            cur->next = q;
            q = q->next;
        }
        cur = cur->next;
    }

    cur->next = (p == nullptr) ? q : p;
    return dummy->next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 递归
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if (list1 == nullptr) return list2;
    if (list2 == nullptr) return list1;

    ListNode* res, * other;
    if (list1->val <= list2->val) {
        res = list1;
        other = list2;
    } else {
        res = list2;
        other = list1;
    }

    res->next = mergeTwoLists(res->next, other);
    return res;
}

LCR 027. 回文链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

ListNode* findMid(ListNode* head) {
    ListNode* dummy = new ListNode();
    dummy->next = head;
    ListNode* slow = dummy;
    ListNode* fast = dummy;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* reverse(ListNode* head) {
    ListNode* next;
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    return pre;
}

// 后半段链表反转，然后和前半段逐个对比
bool isPalindrome(ListNode* head) {
    ListNode* mid = findMid(head);
    ListNode* other = reverse(mid->next);
    mid->next = nullptr;
    ListNode* cur = head;

    while (other != nullptr) {
        if (other->val != cur->val) return false;
        other = other->next;
        cur = cur->next;
    }

    return true;
}

203. 移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ListNode* removeElements(ListNode* head, int value) {
    ListNode* dummy = new ListNode();
    dummy->next = head;
    ListNode* cur = head;
    ListNode* pre = dummy;
    while (cur != nullptr) {
        if (cur->val == value) {
            pre->next = cur->next;
        } else {
            pre = cur;
        }
        cur = cur->next;
    }

    return dummy->next;
}

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

1
2
3
4
5
6
7
8
9
10
11
12

ListNode* deleteDuplicates(ListNode* head) {
    ListNode* pre = head;
    ListNode* cur = head;
    while (cur != nullptr) {
        while (cur != nullptr && cur->val == pre->val) {
            cur = cur->next;
        }
        pre->next = cur;
        pre = pre->next;
    }
    return head;
}

141. 环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) return false;

    struct ListNode *slow = head;
    struct ListNode *fast = head->next;
    // 快慢指针，若有环，快指针迟早会追过慢指针（多跑了一个环的距离）
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}
algorithm, problems
Algorithm Linked list
本文由作者按照 CC BY 4.0 进行授权