链表问题_反转链表

阳光穿透心脏的1/2处 2022-05-21 01:49 265阅读 0赞

题目：输入一个链表的头结点，翻转该链表之后输出头结点。  
分析：翻转一个链表即翻转其连接方向，定义三个指针，pnode表示当前遍历到的节点；p\_pre为pnode的前驱，p\_succ为pnode的后继，之前的连接方向为p\_pre->pnode->p\_succ，将其改为p\_pre<-pnode<-p\_succ即可，在实现的过程中要注意代码的鲁棒性。实现如下：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
      ListNode*ReverseList(ListNode*phead)
      {
          if (phead == NULL)
              return NULL;
    
          ListNode*Reversehead = phead;
          ListNode*pnode = phead;
          ListNode*p_pre = NULL;
          while (pnode)
          {
              ListNode*next = pnode->next;
              if(next==NULL)
                Reversehead = pnode;
    
              pnode->next = p_pre;
              p_pre = pnode;
              pnode = next;       
          }
          return Reversehead;
      }

除上述方法之外，还可以利用递归实现，实现如下：

ListNode* reverseList(List head)
    {
        //如果链表为空或者链表中只有一个元素
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        else
        {
            //先反转后面的链表，走到链表的末端结点
            ListNode*newhead = reverseList(head->next);
            //再将当前节点设置为后面节点的后续节点
            head->next->next = head;
            head->next = NULL;
    
            return newhead;  //newhead在递归中没有变过一直指向最后一个节点，最终被传递出来。
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

相关反转链表

> [剑指Offer 24 反转链表 \[easy\] ][Offer 24 _ _easy_] > ![在这里插入图片描述][watermark_type_ZmFuZ3p

曾经终败给现在/ 2022年12月27日 01:21/ 0 赞/ 203 阅读

相关反转链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

「爱情、让人受尽委屈。」/ 2022年11月29日 12:40/ 0 赞/ 179 阅读

相关反转链表

/ 反转链表给一条单链表，请反转整个链表，并返回反转后的链表 / public class Test5 { / 这个递归函数的定

àì夳堔傛蜴生んèń/ 2022年10月29日 01:50/ 0 赞/ 223 阅读

相关反转链表

代码： // by nby \include<iostream> using namespace std; struct node \{ int

以你之姓@/ 2022年08月07日 07:37/ 0 赞/ 221 阅读

相关反转链表

题目给定一个常数K以及一个单链表L，请编写程序将L中每K个结点反转。例如：给定L为1→2→3→4→5→6，K为3，则输出应该为3→2→1→6→5→4；如果K为4，则输出

た入场券/ 2022年07月28日 01:12/ 0 赞/ 227 阅读

相关链表问题——反转单向链表和双向链表

import java.util.; //单向链表结点 class test{ public class Node{

傷城~/ 2022年06月05日 04:06/ 0 赞/ 262 阅读

相关链表反转

public class LinkedListReverse { public static void main(String[] args) {

￡神魔★判官ぃ/ 2022年05月24日 08:05/ 0 赞/ 272 阅读

相关链表问题_反转链表

题目：输入一个链表的头结点，翻转该链表之后输出头结点。分析：翻转一个链表即翻转其连接方向，定义三个指针，pnode表示当前遍历到的节点；p\_pre为pnode的前驱，p

阳光穿透心脏的1/2处/ 2022年05月21日 01:49/ 0 赞/ 266 阅读

相关反转链表

题目描述输入一个链表，反转链表后，输出新链表的表头。链表的数据结构如下： public class ListNode { int val;

浅浅的花香味﹌/ 2022年05月13日 22:45/ 0 赞/ 281 阅读

相关反转链表

[反转链表][Link 1] 题目描述输入一个链表，反转链表后，输出新链表的表头。 1 public class Solution {

心已赠人/ 2022年03月25日 15:26/ 0 赞/ 250 阅读