首页 > 试题广场 >

反转链表

[编程题]反转链表
  • 热度指数：1761422 时间限制：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
牛客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)
Java
hi_wassuh头像 hi_wassuh 
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) return null;
        ListNode newList = null;
        while(head!=null){
            ListNode temp = head.next; //临时存储
            head.next=newList;         //改箭头
            newList=head;              //指针后移更新新表
            head=temp;                 //指针后移更新旧表
        }
        return newList;
    }
}

发表于 2023-10-10 22:08:09 回复(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) {
        // write code here
        ListNode prev = null;//当前节点的上一个节点
        ListNode curr = head;//当前的节点
        while(curr!=null){
            ListNode nextTemp = curr.next;//临时保存当前节点的下个节点
            curr.next = prev;//当前节点指向上一个节点
            prev = curr;//上一个节点设置成当前节点
            curr = nextTemp;//当前节点设置为下个节点
        }
        return prev;
    }
}

发表于 2023-10-07 16:59:36 回复(0)
Java
练习时长两年半的太平湖水怪很理智头像 练习时长两年半的太平湖水怪很理智 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    //  思路：用新头结点替换原头节点，并将原头节点后移一位，然后再次循环替换、移位，直至原头结点为空，最后返回新的头节点
    public ListNode ReverseList (ListNode head) {
        // write code here
        //创建新的头节点
        ListNode newHead = null;
        // 头节点不为空时进行循环
        while(head!=null){
            // 将头结点的下一个节点赋值给临时节点
            ListNode temp = head.next;
            // 头节点指向新的头节点
            head.next = newHead;
            // 头结点赋值给新的头节点
            newHead = head;
            // 临时节点赋值给头结点，完成头结点后移
            head = temp;
        }
        // 返回新的头节点
        return newHead;
    }
}

发表于 2023-09-20 17:45:07 回复(0)
Java
夹仲见歌头像 夹仲见歌 
public class Solution {
    public ListNode ReverseList (ListNode head){
        if(head==null){
            return null;
        }
        ListNode cur=head,pre=null;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
}
}

发表于 2023-09-16 16:35:05 回复(0)
Java
穿越时空的纸鸢头像 穿越时空的纸鸢
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // 创建头节点
        ListNode tail = new ListNode(0);
        tail.next = head;

        ListNode begin = tail.next;
        ListNode end = tail.next.next;
        //连 掉 接 移
        for (;end != null;){
            begin.next =  end.next;
            end.next = tail.next;
            tail.next = end;
            end = begin.next;
        }
        //头节点不要
        return tail.next;
    }
}

发表于 2023-09-13 19:18:23 回复(0)
Java
最美不过初见2头像 最美不过初见2 
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
        //res用于保存最终结果
        // ListNode res=null;
        // ListNode tail=res;
        // ListNode p=head;
        // while(p!=null){
        //     ListNode tmp=p.next;
        //     p.next=tail;
        //     tail=p;
        //     p=tmp;
        // }
        // return tail;

        //栈
        Stack<ListNode>s=new Stack<>();
        ListNode p=head;
        while(p!=null){
            s.push(p);
            p=p.next;
        }
        ListNode res=new ListNode(-1);
        ListNode tail=res;
        while(!s.isEmpty()){
            ListNode node=s.pop();
            tail.next=node;
            node.next=null;
            tail=node;
        }
        tail.next=null;
        return res.next;
    }
}

发表于 2023-09-11 11:17:56 回复(0)
Java
Sundwich头像 Sundwich
递归解决
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){
return null;
}
//先得到最后的头节点，也就是现在的尾部节点
ListNode tail=head;
while(tail.next!=null){
tail=tail.next;
}
//递归 反转链表
recursionForReverse(head);
return tail;
}

public ListNode recursionForReverse(ListNode node){
if(node==null){
return null;
}
if(node.next==null){
return node;
}
ListNode temp=recursionForReverse(node.next);
node.next=null;
temp.next=node;
return node;
}
}
发表于 2023-08-28 21:42:48 回复(0)
Java
青年阿福头像 青年阿福
Java解题代码，亲测通过 
import java.util.*;


class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public ListNode ReverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode tempNode = head;
        while (tempNode != null) {
            stack.push(tempNode);
            tempNode = tempNode.next;
        }
        if (stack.isEmpty()) {
            return null;
        }
        ListNode node = stack.pop();
        ListNode reversedNode = node;
        while (!stack.isEmpty()) {
            ListNode temNode = stack.pop();
            node.next = temNode;
            node = node.next;
        }
        node.next = null;
        return reversedNode;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNext()) {
            String inputLine = scanner.nextLine().trim();
            ListNode reversedNode;
            Solution solution = new Solution();
            if("{}".equals(inputLine)){
                reversedNode = solution.ReverseList(null);
            }else{
                String[] valueArray = inputLine.substring(1, inputLine.length()-1).split(",");
                if(valueArray.length==1){
                    reversedNode = new ListNode(Integer.parseInt(valueArray[0]));
                }else if(valueArray.length==2){
                    reversedNode = new ListNode(Integer.parseInt(valueArray[1]));
                    reversedNode.next = new ListNode(Integer.parseInt(valueArray[0]));
                } else{
                    ListNode firstNode = new ListNode(Integer.parseInt(valueArray[0]));
                    ListNode secondNode = new ListNode(Integer.parseInt(valueArray[1]));
                    firstNode.next = secondNode;
                    for(int i=2;i<valueArray.length-1;i++){
                        ListNode temNode = new ListNode(Integer.parseInt(valueArray[i]));
                        secondNode.next = temNode;
                        secondNode = secondNode.next;
                    }
                    ListNode endNode = new ListNode(Integer.parseInt(valueArray[valueArray.length-1]));
                    secondNode.next = endNode;
                    endNode.next = null;
                    reversedNode = solution.ReverseList(firstNode);
                }
            }
            solution.printList(reversedNode);

        }

    }


    public void printList(ListNode head) {
        if (head == null) {
            System.out.println("{}");
            return;
        }
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        ListNode curr = head;
        while (curr != null) {
            if (curr.next != null) {
                builder.append(curr.val).append(",");
            } else {
                builder.append(curr.val);
            }
            curr = curr.next;
        }
        builder.append("}");
        System.out.print(builder);
    }
}


发表于 2023-08-06 13:46:29 回复(0)
Java
naivortang头像 naivortang 
    public ListNode ReverseList (ListNode head) {
        // write code here

        // 递归法
        // if(head==null || head.next==null) return head;
        // ListNode  next=ReverseList(head.next);
        // head.next.next=head;
        // head.next=null;

        // return next;

        //遍历法
       if(head==null) return head;
       ListNode prev=null;
       while(head!=null){
           ListNode next=head.next;
           head.next=prev;
           prev=head;
           head=next;
       }

       return prev;
    }

发表于 2023-08-04 13:14:37 回复(1)
Java
牛客101757813号头像 牛客101757813号 
public ListNode ReverseList (ListNode head) {
        // write code here
        if(head == null){
            return null;
        }
        ListNode listNode = new ListNode(head.val);
        while(head.next != null){
            head = head.next;
            ListNode list = new ListNode(head.val);
            list.next = listNode;
            listNode = list;
        }
        return listNode;
    }

发表于 2023-08-02 20:46:00 回复(0)
Java
长久缄默静待雷声头像 长久缄默静待雷声 
 public ListNode ReverseList (ListNode head) {
        // write code here
        //首节点
        ListNode y=head;
        if(y!=null)
        {
            //首节点的后继
            ListNode t=y.next;
            //保存点
            ListNode b=y.next;
            //首节点变尾节点
            head.next=null;
            while(b!=null){
                //预先获取下一个节点
                b=b.next;
                //反转
                t.next=y;
                //待链接节点遍历
                y=t;
                //反转节点遍历
                t=b;
            }
        }
        return y;
    }

发表于 2023-08-02 15:15:34 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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