首页 > 试题广场 >

反转链表

[编程题]反转链表

热度指数：1810701 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： $0\leq n\leq1000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$ 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1

输入

{1,2,3}

输出

{3,2,1}

示例2

输入

{}

输出

{}

说明

空链表则输出空

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

推荐

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

牛客492449568号

请问一下怎么判断传入的为空表？我设置条件为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 回复(1)

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号

//采用了递归思想
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号

//用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

双指针：

    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

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

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

递归解决

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)

提交观点

问题信息

链表

来自：寻找时间黑客在线编程大...

难度：

509条回答 6119收藏 338076浏览

通过挑战的用户

查看代码

牛客11552...

2023-03-14 11:22:15
洞洞鞋小公主

2023-03-12 22:30:58
牛客20133...

2023-03-09 16:07:56
松林子木

2023-03-08 10:28:45
牛客17038...

2023-03-07 15:45:53

反转链表

输入

输出

输入

输出

说明

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题