首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数:1751441 时间限制: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,点此查看相关信息
推荐
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 回复(118)
这是我的,很简单
    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 回复(52)
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)
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *prev = nullptr, *curr = pHead, *next;
        while (curr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};
发表于 2022-01-15 16:16:51 回复(0)
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode * List = NULL;
    struct ListNode * ReversalList = malloc (sizeof(struct ListNode));
     struct ListNode * p = ReversalList;
    while(List != pHead->next){
        List = pHead->next;
        //得到尾节点
        while(List->next ->next != NULL){
            List = List->next;
        }
        if(List == pHead->next){
            break;
        }
        //尾节点赋值给新链表的头节点
        p->next = List->next;
        p = p->next;
        List -> next = NULL;
       }
    return ReversalList;
}
发表于 2021-12-29 11:06:19 回复(0)
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 尾插法:

    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)
/*
双指针
*/
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)
class Solution {
public:
    //最简洁的头插法 
    ListNode* ReverseList(ListNode* pHead) {
    ListNode * p=pHead;
    ListNode *pre=nullptr;//备份好下一个
     while(p!=nullptr)
     {
         ListNode* pNext=p->next;
         p->next=pre;
         pre=p;
         p=pNext;
     }
     return pre;
    }
};
极简至上,简单有效的方法就是最好的
发表于 2021-10-17 12:10:27 回复(0)
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)
之前节点只知道怎么创建和访问,并没有想过怎么反转,看了题解感觉很妙,大概掌握了链表的使用方法了。
1、第一次循环将链表断开,并保存后面的节点到nex中,这样这里只有一个cur节点了,然后我们再将这个节点也就是cur->next指向pre(这个pre第一次循环的时候为空,因为单向链表的最后一项为空)随后将这个cur指针拷贝给pre,这样就形成了pre=cur,pre->next=NULL的新的链表,此时pre节点值为1,同时我们再把后续节点重新赋给cur,方便下一次操作
2、第二次循环,在之前我们已经把后续节点给cur了,那么重复上面的操作,循环将链表断开,并保存后面的节点到nex中,这时候cur节点值为2,pre节点值为1,这时候再把pre给cur->next“接上”,也就是cur->next = pre,也就是说此时cur={2,1},这时候再把pre=cur,与上一步不同的是这时候pre->next=2的节点,后面步骤重复此过程,最后也就得到了一个与之前相反的链表pre
class Solution {    
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex = nullptr; // 这里可以指向nullptr,循环里面要重新指向
        while (cur) {
            nex = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};


发表于 2021-08-31 15:31:22 回复(0)
function ReverseList(head)
{
    let prev = null;
    let curr = head;
    let next = null;
    // ES6语法
    while(curr!=null){
        [curr.next,curr,prev]=[prev,curr.next,curr]
    }
    // ES5语法
    while(curr!==null){
        next = curr,next;
        curr.next = prev;
        curr = next;;
        prev = curr;
    }
    return prev;
}

发表于 2021-08-16 00:30:58 回复(0)
# 人生苦短, 我用python
class Solution:
    def ReverseList(self, pHead):
        p, q = pHead, None
        while(p):
            p, q, q.next = p.next, p, q
        return q

发表于 2021-07-28 10:13:11 回复(0)
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)


运行时间: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)
Python
递: 1->2->3 因为3.next=None 到达终止条件
归: 
3 and 2->3->2 then 2->None so 3->2
2 and 1->2->1 then 1->None so 3->2->1
2020/6/12更新
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
#         2021/6/12 递归方法内存爆了已扑街
#         if not pHead&nbs***bsp;not pHead.next:
#             return pHead
#         pre = self.ReverseList(pHead.next)
#         pHead.next.next=pHead
#         pHead.next=None
#         return pre
#         迭代法
        if not pHead&nbs***bsp;not pHead.next:
            return pHead
        cur = pHead
        pre = None 
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre


编辑于 2021-06-12 23:15:52 回复(0)
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        
        ListNode* pNext = pHead->next;
        pHead->next = NULL;
        ListNode* pCurr = NULL;
        while( pNext!=NULL )
        {
                        // 如果链表有下个节点,就把下个节点作为当前操作节点
            pCurr = pNext;
                        // 同时下个节点指向再后面一个
            pNext = pNext->next;
                        // 当前的这个节点链接到新的链表头部
            pCurr->next = pHead;
                        // 当前这个节点变成新链表的头部
            pHead = pCurr;
        }
        
        return pHead;
    }
};

不知道为啥总提示 段错误,没发现可能出现的异常啊,这种情况也不给看错误时候使用的用例对比了java的代码后发现,居然是没判断指针,所以c++在做题的时候有劣势啊
public class Solution {
    public ListNode ReverseList(ListNode head) {
        
        if( head == null )
           return null;
        
        ListNode _nextNode = head.next;
        head.next = null;
        ListNode _currNode = null;
        while( _nextNode != null )
        {
            _currNode = _nextNode;
            _nextNode = _nextNode.next;
            _currNode.next = head;
            head = _currNode;
        }
        return head;
    }
}

C/C++里加上参数判断后正常了

编辑于 2021-04-02 15:38:03 回复(1)
public class Solution {
    //遍历法
    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode cur=head;
        ListNode ne=null;
        while(cur!=null){  
            head=head.next;
            cur.next=ne;
            ne=cur;
            cur=head;
        }
        return ne;
    }
}
将链表遍历改变链表方向即可。 
发表于 2021-04-01 10:41:38 回复(0)
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)