首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1887385 时间限制：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
cuimarker头像 cuimarker 
两个方法，递归和循环：

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // 方法1
        // return reverse(null, head);
        // 方法2
        ListNode curNode = null;
        while (head != null) {
            ListNode tempNode = head.next;
            head.next = curNode;
            curNode = head;
            head = tempNode;
        }
        
        return curNode;
    }
    private ListNode reverse(ListNode head, ListNode nextNode) {
        if (nextNode == null) {
            return head;
        }
        ListNode tempNode = nextNode.next;
        nextNode.next = head;
        return reverse(nextNode, tempNode);
    }
}


发表于 2025-12-20 18:43:35 回复(0)
Java
英俊的比尔刷牛客头像 英俊的比尔刷牛客 

   public ListNode ReverseList (ListNode head) {
        // write code here
        if(head==null)
        return null;
        ListNode reversedHead = null;
        ListNode current = head;
        ListNode pre = null;
        ListNode temp = null;
        while(current!=null){
            temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }
        reversedHead = pre;
        return reversedHead;
    }

发表于 2025-11-10 14:44:25 回复(0)
Java
丁真中路快封个烟头像 丁真中路快封个烟
结合图里来看吧，我也不知道画得对不对
    public ListNode ReverseList (ListNode head) {
        if(head == null){
            return null;
        }

        ListNode pre = null;
        ListNode cur = head;

        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            // 指针后移
            pre = cur;
            cur = temp;
        }

        return pre;
    }


发表于 2025-08-20 22:57:07 回复(0)
Java
BraveCoder头像 BraveCoder 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // 处理空链表或只有一个节点的情况
        if (head == null || head.next == null) {
            return head;
        }

        ListNode prev = null;    // 前一个节点，初始为null
        ListNode current = head; // 当前节点，从表头开始
        ListNode next = null;    // 下一个节点的临时存储

        while (current != null) {
            next = current.next;  // 先保存下一个节点
            current.next = prev;  // 反转当前节点的指向
            prev = current;       // 移动prev到当前节点
            current = next;       // 移动current到下一个节点
        }

        // 反转完成后，prev成为新的表头
        return prev;
    }
}

发表于 2025-08-07 14:01:51 回复(0)
Java
fortmin头像 fortmin
头插法
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        ListNode list = new ListNode(0);
        while(head != null) {
            ListNode tmp = head.next;
            head.next = list.next;
            list.next = head;
            head = tmp;
        }
        return list.next;
    }
}
发表于 2025-07-03 22:08:09 回复(0)
Java
迷茫的coder在拧螺丝头像 迷茫的coder在拧螺丝
    public ListNode ReverseList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        ListNode pre=null;
        while(head.next!=null){
            ListNode next =head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        head.next=pre;
        return head;
    }
发表于 2025-06-21 00:04:28 回复(0)
Java
牛客522581807号头像 牛客522581807号
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类

     */

    public ListNode result = null;
    public ListNode cur = null;

    public ListNode ReverseList (ListNode head) {
        // write code here
        if(head == null){
            return null;
        }
        //绕圈子用递归
        recursion(head);
        return this.result;

    }

    public ListNode copyNode(ListNode node) {
        return new ListNode(node.val);
    }

    public void recursion(ListNode head) {
        if (head.next != null) {
            recursion(head.next);
            cur.next = copyNode(head);
            cur = cur.next;
        }
        if (head.next == null){
            result = copyNode(head);
            cur = result;
        }
    }
}
发表于 2025-06-10 15:40:26 回复(0)
Java
Solver头像 Solver
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        ListNode pre = null;
        ListNode current = head;
        ListNode next = null;
        ListNode newHead = head;
        while(current != null){
            newHead = current;
            next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return newHead;
    }
}
发表于 2025-05-25 23:41:32 回复(0)
Java
不错哟_2016头像 不错哟_2016
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here// 头结点为空 或者 无后继 直接返回头结点
        ListNode prev = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = prev;

            prev = head;
            head = next;
        }
        return prev;
    }
}
发表于 2025-05-23 11:31:11 回复(0)
Java
活泼的小太阳在炒股头像 活泼的小太阳在炒股 
    public ListNode ReverseList (ListNode head) {
        if ( head ==null || head.next==null ) {
            return head;
        }
        ListNode cur = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }


发表于 2025-01-08 09:21:42 回复(0)
Java
冷艳的做题家在努力头像 冷艳的做题家在努力
请问一下怎么判断传入的为空表？我设置条件为head.next==null,报错NullPointerException 
//判断是否为空链表，若为空链表直接返回空链表
        if(head.next==null){
            return head;
        }
        //头结点设置为priorNode，头结点的next设为currentNode
        ListNode priorNode=head;
        ListNode currentNode = head.next;
        //头结点的next设置为null
        head.next=null;
        while(currentNode.next!=null){//TODO
            //链表反转前记录current的下一个结点
            ListNode tempNode = currentNode.next;
            //链表地址反转操作
            currentNode.next=priorNode;
            //进行下一次链表反转操作前，先将prior和current向后移动以为
            priorNode=currentNode;
            currentNode=tempNode;
        }
        //为最后一个结点执行反转操作
        ListNode tempNode = currentNode.next;
        currentNode.next=priorNode;

        return currentNode;

发表于 2024-09-10 21:47:58 回复(2)
Java
人间水长东头像 人间水长东 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        // 头结点为空 或者 无后继 直接返回头结点
        if (head == null || head.next == null) {
            return head;
        }
        // 定义pre、cur和next
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode next = cur.next;
        // 初始先给头结点，也就是翻转后的尾结点的next置空
        pre.next = null;
        // 循环反转链表
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

发表于 2024-07-26 23:23:58 回复(0)
Java
鲸于向海头像 鲸于向海 
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *  思路：
        初始化一个新的链表节点，用于存储反转后的链表。
        遍历原链表，将每个节点依次插入到新链表的头部。
        返回新链表的头节点。
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        ListNode newHead = null;
            while (head != null) {
                ListNode nextNode = head.next;
                head.next = newHead;
                newHead = head;
                head = nextNode;
            }
            return newHead;
    }
}


发表于 2024-07-21 15:57:40 回复(0)
Java
牛客784614878号头像 牛客784614878号 
//采用了递归思想
public ListNode ReverseList (ListNode head) {
        // write code here
        if(head ==null ||head.next == null){
            return head;
        }
        ListNode cur = ReverseList(head.next);
        head.next.next = head;//节点的下一个指向了自己
        head.next = null;//自己的就断开
        return cur;
    }

发表于 2024-07-19 16:11:40 回复(0)
Java
唉呀妈头像 唉呀妈
public class Solution {
    public ListNode ReverseList (ListNode head) {
        /**
        将原有链表头节点放到新链表的头节点
        1->2->3->4

        第一步：记录原有链表的第二个节点  ListNode o2 = head.next;  
        第二步：将原有链表的头节点放到新链表的头节点，只要原有节点头节点指向新链表的头节点就行  新链表是newNode
                                        head.next = newNode;
        第三步：新链表头节点赋值，将原有链表头节点的值赋给新链表的头节点
                                        newNode = head;
        第四步：将原有链表的第二个节点作为原有链表头节点
                                        head = o2;

        循环重复以上操作 当原有链表为空  循环结束
         */
        ListNode newNode = null;
        while (head != null) {
            ListNode o2 = head.next;
            head.next = newNode;
            newNode = head;
            head = o2;
        }
        return newNode;
    }
}
发表于 2024-05-23 23:52:04 回复(0)
Java
久牛二虎头像 久牛二虎
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        ListNode n = null;
        while(head != null)
        {
            ListNode temp = n;
            n=head;
            head = head.next;
            n.next=temp;
        }
        return n;
    }
}
发表于 2024-05-08 16:02:06 回复(0)
Java
牛客119190309号头像 牛客119190309号
//用list解决这个问题
public ListNode ReverseList (ListNode head) {
        // write code here
        if(head==null||head.next==null)
            return head;
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        ListNode temp = null;
        ListNode res = null;
        for(int i=0;i<list.size();i++){
            res = list.get(i);
            res.next = temp;
            temp = res;
        }
        return res;
    }
发表于 2024-02-28 20:53:17 回复(0)
Java
15zed头像 15zed
双指针： 
    public ListNode ReverseList (ListNode head) {
        if(head == null) return null;//如果给的是空链表，直接返回空
        if(head.next == null) return head;//如果给的链表只有一个节点，不用反转，直接返回
        //如果链表至少是两个节点，才执行下面的代码
        ListNode temp = head.next;//要反转的节点(从第二个节点开始)
        ListNode nextNode = temp.next;//要反转的节点的下一个节点
        head.next = null;//先断开头节点和要反转节点的连接，不然反转完之后会形成环
        //头插法进行反转
        while (temp != null){
            temp.next = head;
            head = temp;
            temp =nextNode;
            if(nextNode != null)
              nextNode = nextNode.next;
        }
        return head;
    }
时间复杂度O(n) 空间复杂度O(1)。

发表于 2024-01-06 15:45:08 回复(0)
Java
春风凉意头像 春风凉意
原地反转链表 
    public ListNode ReverseList (ListNode head) {
        ListNode low = null;
        ListNode fast = head;
        while(fast != null){
            ListNode p = fast.next;
            fast.next = low;
            low = fast;
            fast =p;
        }

        return low;
    }

发表于 2023-12-08 10:42:30 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

反转链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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