数据结构之链表操作详解与示例（反转链表，合并链表，旋转链表，对链表排序）

文章目录

链表是一种常见的基础数据结构，它在内存中的存储方式非常灵活。本文将详细介绍反转链表、合并链表、旋转链表以及对链表排序这四种操作，并提供C和C++的实现示例。

1. 反转链表

反转链表意味着我们需要改变链表中每个节点的指针方向。例如，给定一个链表 1 -> 2 -> 3 -> 4 -> 5，反转后变为 5 -> 4 -> 3 -> 2 -> 1。

算法步骤

1. 初始化三个指针：prev（前一个节点）、curr（当前节点）和next（下一个节点）。
2. 将prev初始化为None，curr初始化为链表的头节点，next初始化为None。
3. 遍历链表，对于每个节点，执行以下操作： 将next设置为curr的下一个节点。 将curr的下一个节点设置为prev。 将prev设置为curr。 将curr设置为next。
4. 最后，prev将是新的头节点，curr将是新的尾节点。

C++实现：

ListNode*reverseList(ListNode* head){
    ListNode* prev =NULL;
    ListNode* curr = head;while(curr !=NULL){
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;}return prev;}

C实现：

ListNode*reverseList(ListNode* head){
    ListNode* prev =NULL;
    ListNode* curr = head;while(curr !=NULL){
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;}return prev;}

2. 合并链表

合并链表意味着将两个或多个链表合并为一个有序链表。这里我们以合并两个升序链表为例。

算法步骤

1. 初始化一个哨兵节点dummy，其下一个节点指向第一个链表的头节点。
2. 使用两个指针分别遍历两个链表，比较当前两个链表的节点的值，将值较小的节点添加到dummy后面，并移动该指针到下一个节点。
3. 当一个链表遍历完成后，将另一个链表的剩余部分直接连接到dummy后面。

C++实现：

ListNode*mergeTwoLists(ListNode* l1, ListNode* l2){if(l1 ==NULL)return l2;if(l2 ==NULL)return l1;if(l1->val < l2->val){
        l1->next =mergeTwoLists(l1->next, l2);return l1;}else{
        l2->next =mergeTwoLists(l1, l2->next);return l2;}}

C实现：

ListNode*mergeTwoLists(ListNode* l1, ListNode* l2){if(l1 ==NULL)return l2;if(l2 ==NULL)return l1;if(l1->val < l2->val){
        l1->next =mergeTwoLists(l1->next, l2);return l1;}else{
        l2->next =mergeTwoLists(l1, l2->next);return l2;}}

3. 旋转链表

旋转链表意味着将链表中的节点进行重新排列，例如，对于一个具有n个节点的链表，我们可以将链表的每个节点移动k个位置（k < n）。如果链表的最后一个节点需要移动到链表的头部，我们可以简单地将链表的头节点和尾节点连接起来。

算法步骤

1. 计算链表中的元素个数n。
2. 计算需要旋转的次数k（k可以是通过给定的步数或数组来确定）。
3. 如果链表长度小于2，直接返回链表。
4. 将链表的尾节点与头节点连接起来。
5. 将新的头节点设置为当前尾节点的下一个节点。

C++实现：

ListNode*rotateRight(ListNode* head,int k){if(head ==NULL|| head->next ==NULL|| k ==0)return head;
    ListNode* old_tail = head;int n;for(n =1; old_tail->next !=NULL; n++)
        old_tail = old_tail->next;
    old_tail->next = head;// 成环
    ListNode* new_tail = head;for(int i =0; i < n - k % n -1; i++)
        new_tail = new_tail->next;
    ListNode* new_head = new_tail->next;
    new_tail->next =NULL;return new_head;}

C实现：

ListNode*rotateRight(ListNode* head,int k){if(head ==NULL|| head->next ==NULL|| k ==0)return head;
    ListNode* old_tail = head;int n;for(n =1; old_tail->next !=NULL; n++)
        old_tail = old_tail->next;
    old_tail->next = head;// 成环
    ListNode* new_tail = head;for(int i =0; i < n - k % n -1; i++)
        new_tail = new_tail->next;
    ListNode* new_head = new_tail->next;
    new_tail->next =NULL;return new_head;}

4. 对链表排序

对链表排序通常指的是对链表中的元素进行排序，以得到一个有序的链表。有多种方法可以实现链表排序，这里我们介绍两种常见的方法：归并排序和快速排序。

归并排序
归并排序是一种分治算法，它将链表分成两半，对每一半递归地进行排序，然后将排序好的两半合并起来。

C++实现：

ListNode*sortList(ListNode* head){if(head ==NULL|| head->next ==NULL)return head;
    ListNode* slow = head,*fast = head,*prev =NULL;while(fast !=NULL&& fast->next !=NULL){
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;}
    prev->next =NULL;// 断开链表
    ListNode* l1 =sortList(head);
    ListNode* l2 =sortList(slow);returnmergeTwoLists(l1, l2);}

ListNode*mergeTwoLists(ListNode* l1, ListNode* l2){if(l1 ==NULL)return l2;if(l2 ==NULL)return l1;if(l1->val < l2->val){
        l1->next =mergeTwoLists(l1->next, l2);return l1;}else{
        l2->next =mergeTwoLists(l1, l2->next);return l2;}}

C实现：

ListNode*sortList(ListNode* head){if(head ==NULL|| head->next ==NULL)return head;
    ListNode* slow = head,*fast = head,*prev =NULL;while(fast !=NULL&& fast->next !=NULL){
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;}
    prev->next =NULL;// 断开链表
    ListNode* l1 =sortList(head);
    ListNode* l2 =sortList(slow);returnmergeTwoLists(l1, l2);}

ListNode*mergeTwoLists(ListNode* l1, ListNode* l2){if(l1 ==NULL)return l2;if(l2 ==NULL)return l1;if(l1->val < l2->val){
        l1->next =mergeTwoLists(l1->next, l2);return l1;}else{
        l2->next =mergeTwoLists(l1, l2->next);return l2;}}

总结

本文介绍了链表的四种常见操作：反转链表、合并链表、旋转链表和对链表排序。每种操作都有其特定的应用场景和算法步骤，通过示例代码展示了如何实现这些操作。理解和掌握这些链表操作对于深入理解数据结构和算法至关重要。