首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1854788 时间限制：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 回复(120)
想去毕业旅行的杨桃在理财头像 想去毕业旅行的杨桃在理财
这是我的，很简单 
    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
TearsTears头像 TearsTears 
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = head;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

发表于 2022-03-08 20:10:39 回复(0)
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)
Rust
卷不动了c头像 卷不动了c

Rust 尾插法：

    pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // write code here
       let mut res=None;
       let mut cur=head;
       while let Some(mut x)=cur{
           cur=x.next;
           x.next=res;
           res=Some(x);
        }
       res

    }

Rust 递归写法：

    pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
       // write code here
         if let None=head{
             return None;
         }
         let mut tmp=head.unwrap();
         match tmp.next {
             None=> return Some(tmp),
             Some(mut x)=>{
                 tmp.next=None;
                 let mut flag=&mut x as *mut Box<ListNode>;

                 let last=self.ReverseList(Some(x));
                 unsafe {
                     (*flag).next=Some(tmp);
                 }
                 return last;
             }
         }
    }
发表于 2021-12-15 11:46:26 回复(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)
Java
A.LL头像 A.LL
1.取出head的第一个节点node追加到result后;
2.head = head.next;
3.设置node到下一个节点为result;
4.result指向node; 
public ListNode ReverseList(ListNode head) {
    ListNode result = null;
    while (head != null){
        ListNode node = head;
        head = head.next;
        node.next = result;
        result = node;
    }
    return result;
}



发表于 2021-09-19 23:01:29 回复(0)
Java
牛客372100818号头像 牛客372100818号
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode reverseHead=new ListNode(0);
        ListNode temp=head;
        ListNode next=null;
        while(temp!=null){
            next=temp.next;
            temp.next=reverseHead.next;
            reverseHead.next=temp;
            temp=next;
        }
        head=reverseHead.next;
        return head;
    }
}
发表于 2021-07-17 13:36:00 回复(2)
Java
牛客521700105号头像 牛客521700105号


运行时间：11ms超过96.16% 用Java提交的代码
占用内存：9704KB超过78.06%用Java提交的代码 
 public class Solution {
    static ListNode p1=null;
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode l=head.next;
        p1=head;
        r(head,l);
        head.next=null;
        return p1;
    }

    //head上一个指针 pre当前指针
    public ListNode r(ListNode head,ListNode pre) {
        if(pre.next==null) {
            pre.next=head;
            p1=pre;
            return head;
        }
    r(pre,pre.next)p.next=head;
        return head;
    }
}

编辑于 2021-05-25 00:19:58 回复(0)
Java
牛客90936758号头像 牛客90936758号
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //采用头插法;
         ListNode now=null;
        while(head!=null){
            ListNode pre=now;//pre保留新生成链表的地址（最开始为null）
            now=head;//生成一个新的元素
            head=head.next;//不要放下面，会被修改
            now.next=pre;//新元素的next指向新生成链表的地址
        }
        return now;
    }
}

编辑于 2021-03-24 02:42:07 回复(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)
sean9626头像 sean9626 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* newpHead=(ListNode*)malloc(sizeof(ListNode));
        newpHead->next=NULL;
        
        for(ListNode * temp=pHead;temp!=NULL;temp=temp->next){
            ListNode* x=(ListNode*)malloc(sizeof(ListNode));
            x->val=temp->val;
            x->next=newpHead->next;
            newpHead->next=x;
        }
        
        return newpHead->next;
    }
};
上面是AC代码
之前有过错误：段错误。发现在循环里面 
ListNode x(temp->val)
这样开结点的话，受循环影响每次会回收重开，那么后面 
newpHead->next=&x
调试时&x位置实际上不变的，也就是说开节点全在同一个地方。
到最后就是一个一个结点的自循环的链表了。

这个错误还是太不应该了，要注意。
发表于 2021-01-24 23:56:01 回复(0)
C/C++
小海小亮头像 小海小亮
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
                 //临时节点   新的头节点
        ListNode * tmpHead ;
        ListNode *resultHead = pHead;
        while(pHead != NULL&&pHead->next!=NULL)
        {
            tmpHead = pHead->next;
            pHead->next = tmpHead->next;
            tmpHead->next = resultHead;
            resultHead = tmpHead;
        }
        return resultHead;
    }
};
发表于 2020-10-14 16:42:19 回复(0)
C/C++
马里奥起飞头像 马里奥起飞
C++
三个ListNode* pre, pHead, next  分别指向前一个节点，当前节点，下一个节点。 

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) 
    {
        if (!pHead) return pHead;
        ListNode* pre = nullptr;
        ListNode* next = pHead->next;
        while (next != nullptr)
        {
            pHead->next = pre;
            pre = pHead;
            pHead = next;
            next = next->next;
        }
        pHead->next = pre;
        return pHead;
    }
};


发表于 2020-09-08 17:42:07 回复(0)
wmcxzy头像 wmcxzy
    ListNode* ReverseList(ListNode* pHead) 
    {
        if (!pHead) return nullptr;
        ListNode *p1 = pHead;
        ListNode *p2 = pHead->next;
        while(p2)
        {
            p1->next = p2->next;
            p2->next = pHead;
            pHead = p2;
            p2 = p1->next;
        }
        return pHead;
    }
发表于 2020-08-31 11:39:24 回复(0)
C/C++
漫漫云天自翱翔头像 漫漫云天自翱翔
利用头插法 
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode* newpHead=NULL;//NULL代表为反转链表得末尾
        while(pHead!=NULL){//当前不为空
            ListNode* temp=pHead->next;//拿到他下一个节点
            pHead->next=newpHead;//头插法，插在newpHead得前面
            newpHead=pHead;//newphead变成新链表得头节点
            pHead=temp;//反转下一个节点
        }
        return newpHead;
    }
};

发表于 2020-08-25 10:00:34 回复(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)
zzucj头像 zzucj 
public ListNode ReverseList(ListNode head) {
    ListNode tail = null;
    while (head != null) {
        ListNode k = tail;
        tail = head;
        ListNode nxt = head.next;
        head.next = k;
        head = nxt;
    }
    return tail;
}
还有没有比我更简单的
发表于 2020-07-08 10:39:29 回复(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)
Java
现实理想青年头像 现实理想青年 
/*  这题的关键点要存下当前节点的前一个节点、当前点以及当前点后一个节点，以免出现节点丢失的问题。  在一开始可以把head当作当前点,null作为前一个点prenode，head.next作为后一个点aftnode  然后把当前点head指向prenode，此时head变化为新的prenode，aftnode变为新的head，  新的head.next变成aftnode，循环继续。  直到当前点的下下个节点为空，不能生成新的aftnode时，说明只剩最后两个点，逆序输出即可。  */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode prenode = null;
        ListNode aftnode = head.next;
        while(head.next.next != null){
            head.next = prenode;
            prenode = head; //当前节点保留作为下一个节点的前一个节点
            head = aftnode;   //当前节点后移
            aftnode = head.next; //保留下一个节点
        }
        head.next = prenode;
        aftnode.next = head;
        return aftnode;
    }
}


发表于 2020-04-08 16:23:06 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

反转链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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