反转链表（c实现）

Love The Way You Lie 2022-11-17 13:50 130阅读 0赞

关于链表的两个小题：  
第一个小题：  
![在这里插入图片描述][20210409191901493.png]  
刚看到这个题目，一脸懵，其实这个题目考察我们对链表的理解，接下来说一下具体的解题方法：删掉该结点后面的一个节点，然后将该结点的值赋值为其后面一个结点的值。

具体代码：

void DeleteRandomNode(ListNode *pCurrent)
    { 
         ListNode *pNext = pCurrent->next;
         if(pNext != NULL)
         { 
              pCurrent->next = pNext->next;
              pCurrent->val = pNext->val;
         }
         free(pNext);
    }

第二个小题：就是力扣上的反转链表的问题

示例:  
输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reverse-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于这个问题，首先最容易想到的是遍历的方式解决，将当前节点的  next n e x t \\textit\{next\}next nextnext指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。另外在更改指向之前，还需要存储后一个节点，最后返回新的头引用。代码如下：

struct ListNode* reverseList2(struct ListNode* head){ 
         if(head->next==NULL || head == NULL)
              return head;
         struct ListNode* pre = NULL;
         struct ListNode* curr = head;
         while(curr != NULL)
         { 
              struct ListNode* pnext = curr->next;
              curr->next = pre;
              pre = curr;
              curr = pnext;
         }
         return pre;
    }

时间复杂度O(n)，空间复杂度O(1)

第二种方式就是递归的方式，先放上代码：

struct ListNode* reverseList(struct ListNode* head){ 
         if(head->next==NULL)
              return head;
         struct ListNode* last = reverseList(head->next);
         head->next->next = head;
         head->next = NULL;
         return last;
    }

时间复杂度O(n)，空间复杂度O(n)，递归操作导致。  
这种方式是我在看labuladong的文章后理解的，感觉他讲的特别好，这里[推荐一下][Link 1]，对于递归很长一段时间直至现在我还有些理解不了，因为我总是会陷入到实现细节，不过看了labuladong讲的递归之后，我觉得自己有些新的认识。

下面就是他讲的内容：

对于递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverse 函数定义是这样的： 输入一个节点 head，将「以 head为起点」的链表反转，并返回反转之后的头结点。  
  
那么输入 reverse(head) 后，会在这里进行递归：struct ListNode\* last = reverseList(head->next);注意不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：按照我们reverse 函数的定义，这条语句执行完成之后，输入一个节点 head->next，将「以 head->next为起点」的链表反转，并返回反转之后的头结点。  
反转之后的效果是这样的：此时head->next结点的next域为NULL，反转之后返回的就为原链表的最后一个结点的指针，用last指针接收了。  
  
再来看下面的这句代码head->next->next = head;经过上面的处理之后，从head的后一个结点到末尾完成了反转，我们需要将之与head结点连接起来，所以head->next->next = head是让head->next结点指向head。  
  
再来看最后一句代码：head->next = NULL;此时整个链表完成了反转，还需要将原链表的头节点的next域设置为NULL。  
需要注意：  
1、递归函数要有 base case，也就是这句：  
if(head->next==NULL) return head;  
意思是如果链表只有一个节点的时候反转也是它自己，直接返回即可。  
2、当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：

labuladong的github：  
https://github.com/jiajunhua/labuladong-fucking-algorithm（个人觉得讲的很好，推荐一下）

--------------------

在labuladong的文章里面还有一些扩展问题，下面也记录一下：

反转链表的前n个结点

递归方法：

struct ListNode* temp = NULL;
    struct ListNode* reverseListN(struct ListNode* head, int n){ 
         if(head->next==NULL||n==1)
         { 
              temp = head->next;
              return head;
         }
         struct ListNode* nlast = reverseListN(head->next, n-1);
         head->next->next = head;
         head->next = temp;
         return nlast;
    }

和反转整个链表非常相似，主要的区别：

1、递归的base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。  
2、刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。

给一个索引区间 \[m,n\]（索引从 1 开始），仅仅反转区间中的链表元素

struct ListNode* reverseListMN(struct ListNode* head, int m, int n)
    { 
         if(m == 1)
         { 
              return reverseListN(head, n);
         }
         head->next = reverseListMN(head->next, m-1, n-1);
         return head;
    }

首先，如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：  
struct ListNode\* reverseListMN(struct ListNode\* head, int m, int n)  
\{  
// base case  
if(m == 1)  
\{  
return reverseListN(head, n);  
\}  
// …  
\}  
  
如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

struct ListNode* reverseListMN(struct ListNode* head, int m, int n)
    { 	//base case
         if(m == 1)
         { 
              return reverseListN(head, n);
         }
         //前进到反转的起点触发 base case
         head->next = reverseListMN(head->next, m-1, n-1);
         return head;
    }

> 递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。  
> 处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。  
> 值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

--------------------

反转链表的前n个结点  
遍历方式：

struct ListNode* reverseListN2(struct ListNode* head, int n){ 
         struct ListNode* pre = NULL;
         struct ListNode* curr = head;
         while(n>0)
         { 
              struct ListNode* pnext = curr->next;
              curr->next = pre;
              pre = curr;
              curr = pnext;
              n--; //计数
         }
         head->next = curr; //头结点指向第n个结点的后面
         return pre; //返回第n个结点的指针,此时该结点为头节点
    }

给一个索引区间 \[m,n\]（索引从 1 开始），仅仅反转区间中的链表元素

void reverseLinkedList(struct ListNode *head) { 
        // 也可以使用递归反转一个链表
        struct ListNode *pre = NULL;
        struct ListNode *cur = head;
    
        while (cur != NULL) { 
            struct ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
    }
    
    struct ListNode *reverseBetween(struct ListNode *head, int left, int right) { 
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        struct ListNode *dummyNode = malloc(sizeof(struct ListNode));
        dummyNode->val = -1;
        dummyNode->next = head;
    
        struct ListNode *pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) { 
            pre = pre->next;
        }
    
        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        struct ListNode *rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) { 
            rightNode = rightNode->next;
        }
    
        // 第 3 步：切断出一个子链表（截取链表）
        struct ListNode *leftNode = pre->next;
        struct ListNode *curr = rightNode->next;
    
        // 注意：切断链接
        pre->next = NULL;
        rightNode->next = NULL;
    
        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);
    
        // 第 5 步：接回到原来的链表中
        pre->next = rightNode;
        leftNode->next = curr;
        return dummyNode->next;
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[20210409191901493.png]: /images/20221022/2c7b7b8d248c4b1c910686f934e11393.png
[Link 1]: https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/shou-ba-shou-shua-lian-biao-ti-mu-xun-lian-di-gui-si-wei/di-gui-fan-zhuan-lian-biao-de-yi-bu-fen