正文

掌握单链表，轻松解决这些经典习题

/0 浏览量
0413

在计算机科学中，链表是一种常见的基础数据结构。而单链表作为链表的一种，因其简单和灵活而被广泛使用。今天，我们就来探讨一下单链表的相关知识，并通过一些经典习题来加深理解。

单链表的基本概念

定义

单链表是由一系列结点组成的线性序列，每个结点包含两部分：数据域和指针域。数据域用来存储数据，指针域用来指向下一个结点。

结构

struct ListNode {
    int val;
    struct ListNode* next;
};

特点

  1. 无序性：单链表中的结点顺序可以根据需要进行调整。
  2. 动态性：单链表的大小可以动态变化。
  3. 空间复杂度：单链表的空间复杂度较高，因为每个结点都需要存储指针。

经典习题

1. 反转链表

题目描述：输入一个单链表的头结点，反转该链表并返回新链表的头结点。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* next = NULL;
    while (curr != NULL) {
        next = curr->next; // 保存下一个结点
        curr->next = prev; // 反转当前结点
        prev = curr;       // 移动指针
        curr = next;       // 移动指针
    }
    return prev; // 新链表的头结点
}

2. 合并两个有序链表

题目描述：输入两个有序单链表的头结点，合并为一个新的有序单链表并返回。

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* tail = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy->next;
}

3. 删除链表的倒数第k个结点

题目描述：输入一个单链表的头结点和一个整数k，删除链表的倒数第k个结点并返回新的链表头结点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* fast = dummy;
    struct ListNode* slow = dummy;
    while (n--) {
        fast = fast->next;
    }
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummy->next;
}

总结

通过以上几个经典习题，我们可以更好地理解单链表的基本操作和特点。在解决实际问题时，灵活运用单链表的相关知识，可以帮助我们更高效地解决问题。希望这篇文章能对你有所帮助！

-- 展开阅读全文 --