首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1898558 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围：
要求：空间复杂度 ，时间复杂度 。

如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例1

输入

{1,2,3}

输出

{3,2,1}
示例2

输入

{}

输出

{}

说明

空链表则输出空

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
writezen头像 writezen 
public class Solution {
 public static ListNode ReverseList(ListNode head) {
 if(head==null)
 return null;
 ListNode reversedHead=null;
 ListNode current=head;
 ListNode tmp=null;
 ListNode pre=null;
 while(current!=null){
 tmp=current.next;
 current.next=pre;
 if(tmp==null)
 reversedHead=current;
            pre=current;
 current=tmp;
 
 }
 return reversedHead;
 }
}

编辑于 2015-06-19 16:46:40 回复(64)
我就用这个名字了头像 我就用这个名字了
Java   循环操作   详细思路 
public class Solution {
    public ListNode ReverseList(ListNode head) {
      
        if(head==null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
    	ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

编辑于 2021-01-20 17:13:50 回复(121)
想去毕业旅行的杨桃在理财头像 想去毕业旅行的杨桃在理财
这是我的，很简单 
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
        	next = head.next;
        	head.next = pre;
        	pre = head;
        	head = next;
        }
		return pre;
    }

发表于 2016-02-16 09:14:35 回复(53)
Java
Treasure☞头像 Treasure☞ 
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str=null;
        while((str = in.readLine()) != null){
            String[] str1 = str.split("[^0-9]");
            StringBuffer str2 = new StringBuffer();
            str2.append("{");
            for(int i=str1.length-1;i>0;i--){
                if(i==1){
                    str2.append(str1[i]);
                    break;
                }
                str2.append(str1[i] + ",");
            }
            str2.append("}");
            System.out.print(str2.toString());
        }
    }
}

发表于 2021-12-25 17:11:23 回复(0)
Java
LDew头像 LDew 
/*
双指针
*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        //存储t2.next 因为要将t2.next设为t1，所以需要记录
        ListNode tmp = null;
        //相邻的两个节点
        ListNode t1 = head;
        ListNode t2 = head.next;
        do{
            tmp = t2.next;
            t2.next = t1;
            t1 = t2;
            t2 = tmp;
        }while(t2 != null);
        //头节点需要设置一下，不然在第一个节点和第二个节点会产生环
        head.next = null;
        return t1;
    }
}
还可以直接模拟，可以看我写的题解
发表于 2021-10-27 19:08:29 回复(0)
威猛的安哥拉兔在拧螺丝头像 威猛的安哥拉兔在拧螺丝 
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode p1=head;
        ListNode p2=head;
        ListNode root=head;
        if(head == null){
            return null;
        }
        int k = 1;
        while(p1.next != null){
            p1=p1.next;
            k++;
        }
        int[] m=new int[k];
        for(int i=0;i<k;i++){
            m[i]=p2.val;
            p2=p2.next;
        }
        ListNode p=root;
        while(k>0){
            root.next=new ListNode(m[k-1]);
            root=root.next;
            k--;
        }
        return p.next;
    }
}

笨方法，创建一个数组记录数字，然后重新搞一个链表出来。
发表于 2021-03-19 14:31:56 回复(0)
C/C++
牛客小兴头像 牛客小兴
C++
前插法： 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL) return pHead;
        ListNode* dummy = new ListNode(-1);
        dummy->next = pHead;
        ListNode* cur = dummy->next;
        ListNode* temp = NULL;
        while(cur->next){
            temp = cur->next;
            cur->next = temp->next;
            temp->next = dummy->next;
            dummy->next = temp;
        }
        return dummy->next;
    }
};
双指针： 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL || pHead->next == NULL) return pHead;
        ListNode* pre = NULL;
        ListNode* cur = pHead;
        ListNode* temp = NULL;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};



发表于 2020-08-05 11:10:05 回复(0)
枸杞很好头像 枸杞很好 
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode current = head;
        while(current != null){
            ListNode tempNode = current.next;
            current.next = pre;
            pre = current;
            current = tempNode;
        }
        return pre;
    }
}
发表于 2020-04-09 17:48:47 回复(0)
C/C++
牛客123313头像 牛客123313
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL) return NULL;//鲁棒性
        ListNode* pre=NULL;
        ListNode* cur=pHead;
        ListNode* temp=pHead;
        
        while(cur!=NULL)
        {//三个指针在链表上同时滑动
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};
发表于 2020-01-14 17:33:07 回复(0)
G凯learlove头像 G凯learlove
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if pHead == None:
            return pHead
        elif pHead.next == None:
            return pHead
        else:
            current = pHead
            t_next = pHead.next
            tc_next = t_next.next
            current.next = None
            t_next.next = current
            current = t_next
            t_next = tc_next
            tc_next = tc_next.next
            while tc_next !=None:
                t_next.next = current
                #return t_next
                current = t_next
                t_next = tc_next
                tc_next = tc_next.next
            t_next.next = current
            return t_next
#利用三个指针确保后续的节点不丢失
#然后第二个指针的next指向第一个指针指向的节点，第三个指针保持原来还剩下的链表。这样依次循环直到结束

       
发表于 2019-08-14 22:44:36 回复(1)
Java
kaname233头像 kaname233 
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode next = head, temp = null;
        while(head != null){
            next = head.next;
            head.next = temp;
            temp = head;
            head = next;
        }
        return temp;
    }
}
可能是最简洁的了
发表于 2019-08-08 15:26:34 回复(0)
Java
七201904092031392头像 七201904092031392
public ListNode ReverseList(ListNode head) {
            if(head==null)
                return null;
            ListNode pre=head;
            while(head.next!=null){
                ListNode newHead=null;
                newHead=head.next;
                head.next=head.next.next;
                newHead.next=pre;
                pre=newHead;
            }
            return pre;
    }
发表于 2019-08-01 10:06:46 回复(2)
C/C++
君莫笑201810180823161头像 君莫笑201810180823161
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) { // 即采用头插法，插入链表
        if(!pHead)
            return NULL;
        ListNode *p = pHead;
        ListNode *q;
        ListNode *s = NULL; // s保存上一个节点信息
        while(p){ // p为原链表，按照它的顺序进行头插法建立链表，则能实现反转的效果
            q = new ListNode(p->val);
            q->next = s;
            s = q;
            p = p->next;
        }
        return s;
    }
};

发表于 2019-05-11 11:07:29 回复(0)
C/C++
thewanted头像 thewanted 
  ListNode* ReverseList(ListNode* pHead) {
        ListNode* p1 = NULL;
        ListNode* p2 = pHead;
        while (p2 != NULL){
            ListNode* temp;
            temp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = temp;
        }
        return p1;
    }

发表于 2019-04-18 16:09:50 回复(0)
陶亚凡头像 陶亚凡 
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        
        p_last = None
        p = pHead
        
        while p:
            p.next, p, p_last = p_last, p.next, p
            
        return p_last

发表于 2019-04-16 13:11:53 回复(0)
可爱又迷人的zcc头像 可爱又迷人的zcc 
import java.util.Stack;
/**
 * 反转链表：核心方法 通过栈来反转链表
  *先将链表入栈，然后将链表依次出栈，出栈结点的next指向当前栈的栈顶结点
  *(实现核心功能后考虑健壮性问题)
 * 考虑特殊情况 ：
 * 1.head为空
 * 2.链表长为1
 * 3.链表特别长
 * @author zzc
 */
public class solution {     public ListNode ReverseList(ListNode head) {         if(head==null){             return null;         }
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode node=head;
        while(node!=null){
            stack.add(node);
            node=node.next;
        }
        ListNode rhead=stack.peek();
        while(!stack.empty()){       
            node=stack.pop();
            if(!stack.empty()){
                node.next=stack.peek();
            }else{
                node.next=null;
            }
    }
        return rhead;
}
}

编辑于 2019-04-14 11:13:55 回复(0)
绿叶萌飞头像 绿叶萌飞 
// 基础版
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null)    return null;
        if (head.next == null)    return head;
        ListNode lastNode = head, curNode = head.next, nextNode = head.next.next;
        lastNode.next = null;
        while (curNode.next != null) {
            curNode.next = lastNode;
            lastNode = curNode;
            curNode = nextNode;
            nextNode = nextNode.next;
        }
        curNode.next = lastNode;
        return curNode;
    }
}

// 简洁版
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode last = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

发表于 2018-12-08 15:33:24 回复(0)
Java
InseQM头像 InseQM

public class ReverseList {
//循环
public ListNode demo1(ListNode head){
if (head == null){
return null;
}
ListNode pre = null;
ListNode next;
while (head != null){
//保存head的下一个节点，防止断开链后找不到下一个节点
next = head.next;
//将head节点的下一个节点指向前一个节点pre，实现链表反转
head.next = pre;
pre = head;
head = next;
}
return pre;
}
//递归
public ListNode demo2(ListNode head){
if (head == null || head.next == null){
return head;
}
//递归出原链表尾部节点node
ListNode node = demo2(head.next);
//将原链表从后向前一个个置于原链表尾部后面，并将原链表置为null
(head.next).next = head;
(head.next) = null;
return node;
}
}

发表于 2018-08-09 17:33:33 回复(0)
文中序头像 文中序 
 public ListNode ReverseList(ListNode head){
        /*
        头插法
         */
        /*ListNode NewHead=null,Next=head,Temp=null;
        if(head==null||head.next==null)
            return head;
        while (Next!=null){
            Temp=Next.next;
            Next.next=NewHead;
            NewHead=Next;
            Next=Temp;
        }
        return NewHead;*/


        /*
        递归解法
         */

        if(head==null||head.next==null)
            return head;
        ListNode NewHead=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        return NewHead;
    }
发表于 2018-07-07 15:27:06 回复(1)
Java
Mr.『黑』℡头像 Mr.『黑』℡ 
/*
输入一个链表，反转链表后，输出链表的所有元素
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //head：当前节点
    public ListNode ReverseList(ListNode head) {
        //先定义两个变量，分别指向head前和后
       ListNode prev = null ;
       ListNode last = null ;
           
         //当前节点不为空
        while ( head != null )
        {
        //先记录当前节点的下一个
          last = head.next ;
          //反转，即将当前节点的下一个节点指向前一个节点
          head.next = prev ;
          //当前节点反转完毕，将其作为下一个节点的前一个节点记录下来
          prev = head ;
          //当前节点指向下一个
          head = last ;
        }
        //当前节点为空了，说明反转到最后了，将其前一个即新的首节点返回
        return prev ;
    }
}

发表于 2018-05-23 14:16:30 回复(0)
C/C++
三篠头像 三篠
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //利用栈
        /*if(!pHead) return NULL;
        stack<int> s;
        ListNode* p = pHead;
        while(p){
            s.push(p->val);
            p = p->next;
        }
        for(p=pHead;p;p=p->next){
            p->val = s.top();
            s.pop();
        }
        return pHead;*/
        
        //直接反转
        if(!pHead) return NULL;//空链表
        ListNode *p=pHead;
        ListNode *q=pHead->next;
        pHead->next = NULL;
        if(!q) return pHead;//单节点链表
        ListNode *temp;
        while(q){
            temp = q->next;
            q->next = p;
            p = q;
            q = temp;
        }
        return p;
    }
};

编辑于 2018-04-22 13:28:37 回复(0)
提交观点

问题信息

链表
来自：寻找时间黑客在线编程大...
难度：
3094条回答 348531浏览

热门推荐

通过挑战的用户

查看代码

相关试题

反转链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号