首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1882820 时间限制：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)
Rust
老刘001头像 老刘001 
/**
 *  #[derive(PartialEq, Eq, Debug, Clone)]
 *  pub struct ListNode {
 *      pub val: i32,
 *      pub next: Option<Box<ListNode>>
 *  }
 * 
 *  impl ListNode {
 *      #[inline]
 *      fn new(val: i32) -> Self {
 *          ListNode {
 *              val: val,
 *              next: None,
 *          }
 *      }
 *  }
 */
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param head ListNode类 
        * @return ListNode类
    */
    pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // write code here
        let mut p1 = None;
        let mut p2 = head;
        // a -> b -> c
        // p1   p2   p3
        
        // target
        // a <- b <- c
        
        while p2.is_some() {
            // unlink nodes
            let mut p3 = p2.as_mut().unwrap().next.take();
            // let mut p4 = p3.as_mut().unwrap().next.take();
            // println!("{:?}", p2);
            // println!("{:?}", p3);
            // println!("{:?}", p4);
            
            // make p1 <- p2,  p3
            p2.as_mut().unwrap().next = p1;

            // move to next
            p1 = p2;
            p2 = p3;


            // todo!();
        }

        // let mut p2 = head;
        //let mut p3 = 
        // println!("{:?}", p2);
        // println!("{:?}", head);
        p1
    }
}

发表于 2023-08-13 20:35:30 回复(0)
Rust
黃建榮头像 黃建榮 
trait DoubleLinkList {
    fn ReverseList(&self, mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // write code here
        let mut pre = None;
        while let Some(mut node) = head {
            head = node.next.take();
            node.next = pre;
            pre = Some(node);
        }
        pre
    }
}

发表于 2023-03-24 20:00:52 回复(0)
Rust
Gopher015头像 Gopher015 
struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    * 
        * @param head ListNode类 
        * @return ListNode类
    */
    pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut pre: Option<Box<ListNode>> = None;
        let mut cur: Option<Box<ListNode>> = head;
        // 获取当前节点
        while let Some(mut node) = cur.take() {
            // 当前节点移动到下一个节点: 先移动, 就不用暂存这个下一个节点了
            // 这是因为while里面匹配了节点node, 就是cur, 相当于暂存了cur, 所以不用定义中间变量
            cur = node.next;
            // 当前节点的下一个节点指向前面, 反转
            node.next = pre;
            // 前一个移动到下一个节点
            pre = Some(node);
        }
        pre    
    }
}

发表于 2022-11-12 18:01:36 回复(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 回复(1)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

反转链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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