首页 > 试题广场 > 反转链表
[编程题]反转链表
输入一个链表,反转链表后,输出新链表的表头。

151个回答

添加回答
推荐
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 回复(40)
    public ListNode ReverseList(ListNode head) {
        ListNode node=head;
        int[] array=new int[10];
        int i=0;    //标志
        while(head!=null) {
            array[i++]=head.val;
            head=head.next;
        }
        i--;
        head=node;
        while(head!=null) {
            head.val=array[i--];
            head=head.next;
        }
        return node;
    }
发表于 2019-05-01 23:29:31 回复(0)
public class Solution {
   
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode listNode = null;
        ListNode listNode1 = head;
        while (head!=null){
            head=head.next;
            listNode1.next=listNode;
            listNode=listNode1;
            listNode1=head;
        }

        return listNode;
    }
}
方法比较粗糙
发表于 2019-04-25 18:06:03 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;  // 用来保存上一个节点
        ListNode temp = null; // 临时节点 保存下一个要遍历的节点
        while(head!=null){
            temp = head.next; // 保存下一个要遍历的节点
            head.next = pre;  // 当前节点指向前一个节点
            pre = head;       // 更新前一个节点为当前节点
            head = temp;      // 更新当前节点为下一个要遍历的节点
        }
        return pre;
    }
}
发表于 2019-04-17 17:01:47 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        
        ListNode pre = null;
        ListNode next = null;
        
        if(head == null)
            return null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        
        return pre; 
    }
}

发表于 2019-04-16 21:06:43 回复(0)
反序第一反应是stack,将链表的值存在栈中,然后再新建一个链表把栈中的数弹出来。
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        Stack<Integer> stack = new Stack<Integer>();
        while (head != null) {
//老链表的数存入栈,直到为空
            stack.add(head.val);
            head = head.next;
        }
//把栈顶的数存起来输出
        ListNode reversHead = new ListNode(stack.pop());
        ListNode tmpNode = reversHead;
        while (!stack.isEmpty()) {
//新建链表,把栈中元素一 一弹出
            tmpNode.next = new ListNode(stack.pop());
            tmpNode = tmpNode.next;
        }
        return reversHead;
    }
}
发表于 2019-04-15 08:37:09 回复(0)
我感觉自己的也不错,只不过写了好几天
public class Solution {
    public ListNode ReverseList(ListNode head) {
       ListNode nh = null;
       ListNode temp = null;
        if(head==null) return null ;
       while(head.next!=null){
           temp = head.next;
           head.next = nh ;
           nh = head ;
           head = temp ;
       }
       head.next = nh ;
       nh = head ;
      return nh ;
    }
}

发表于 2019-03-30 10:26:04 回复(0)
思路分析:定义三个节点,pre:保存前一个节点(指向current);current:
保存当前节点(指向current.next);tmp:保存下一个节点(指向current.next的下一个节点);
首先tmp = current.next;//存好下一个节点的指向,然后改变下一个节点的指向,使其指向
current,即current.next = pre;再让pre移到current;current移到current.next.
结果使current.next指向了current,如此循环,直到current==null。
发表于 2019-03-28 10:18:46 回复(0)
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode p=null;
        ListNode q=head;
        ListNode r=q.next;
        while(r!=null){
            r=q.next;
            q.next=p;
            p=q;
            q=r;
        }
       return p;
    }
}
发表于 2019-03-17 22:48:26 回复(0)
 public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode nex = null;
        while(head != null){
            nex = head.next;
            head.next = pre;
            pre = head;
            head = nex;
        }
        return pre;
    }
}

发表于 2019-03-16 23:29:22 回复(0)
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)return null;
        ListNode temp = head.next;
        ListNode tempa = head;
        ListNode tempb = null;
        while(temp!=null){
            tempb = temp.next;
            temp.next = tempa;
            tempa = temp;
            temp = tempb;
        }
        head.next =  null;
        return tempa;
    }
}

发表于 2019-03-16 20:38:16 回复(0)
好像没有人使用Java栈的方法来实现。利用栈的先进后出的特征,使链表反转。
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode listNode = head;
        ListNode newHead;
        if(head == null )
            return null;
        Stack<ListNode> stack = new Stack<ListNode>();
        
        while(listNode.next !=null){          
            stack.push(listNode);
            listNode = listNode.next;
        }
        newHead = listNode;//使newHead指向listNode
        while(!stack.isEmpty()){
            listNode.next = stack.pop();//取出栈顶元素并删除
            listNode = listNode.next;
            
        }
        listNode.next=null;//最后别忘了表尾指向null
        return newHead;
    }
}

发表于 2019-03-13 20:22:03 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode pNode = head;
        ListNode reversedHead = null;
        while(pNode != null){
            ListNode next = pNode.next;
            if(next == null){
                reversedHead = pNode;
            }
            pNode.next = pre;
            pre = pNode;
            pNode = next;
        }
        return reversedHead;
    }
}


编辑于 2019-03-12 22:48:26 回复(0)
来自讨论区
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
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;
    }
}


发表于 2019-03-12 15:18:31 回复(0)
Java方法一:迭代法
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}
Java方法二:递归法
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        
        ListNode newHead = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

发表于 2019-03-08 15:32:47 回复(0)

题目描述

输入一个链表,反转链表后,输出新链表的表头。

解题思路

一开始学的时候看的答案就是这个方法,显然是要比递归好的,但是如果不理解的话,光靠背很容易出错,并且也不大背的上,如今重温这道题,其实是很简单的,我们下面用图示来阐述。

主要的思想是用两个指针,其中newHead指向的是反转成功的链表的头部,currentHead指向的是还没有反转的链表的头部:

image

初始状态是newHead指向nullcurrentHead指向的是第一个元素,一直往后遍历直到newHead指向最后一个元素为止:

image

下面展示的是其中某个时间点的指向细节:

image

理解了上面的图示,程序就呼之欲出了。

我的答案

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode newHead = null;
        ListNode currentHead = head;
        if(head == null || head.next == null){
            return head;
        }

        while(currentHead != null){
            ListNode next = currentHead.next;
            currentHead.next = newHead;
            newHead = currentHead;
            currentHead = next;
        }

        return newHead;
    }
}
发表于 2019-03-07 11:35:30 回复(0)
java 递归
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode temp = head.next;
        ListNode newhead = ReverseList(temp);
        temp.next = head;
        head.next = null;
        return newhead;
    }
}

发表于 2019-03-04 15:31:51 回复(0)
 public ListNode ReverseList(ListNode head) {
 if (head == null || head.next == null) {
 return head;
 }
 ListNode pre = head; // 前驱节点初始化为头节点
 ListNode p = pre.next; // 当前节点为前驱节点的next
 pre.next = null; // 头节点的next首先变为null
 while (p.next != null) { // 当前节点还有后继节点时
 ListNode next = p.next; // 保存后继节点
 p.next = pre; // 当前节点的next反转为前驱节点
 pre = p; // 前驱节点后移变为当前节点
 p = next; // 当前节点后移变为后继节点
 }
 p.next = pre; // 最后将当前节点的next反转为前驱节点
 return p;
}
编辑于 2019-03-03 12:12:57 回复(0)

package linked.list;
//题目描述
//输入一个链表,反转链表后,输出新链表的表头。
public class ResverList {
    public static void main(String[] args) {
        ResverList kn = new ResverList();
        ListNode01 ln = new ListNode01(1);
        ln.next = new ListNode01(2);
        ln.next.next = new ListNode01(3);
        ln.next.next.next = new ListNode01(4);
        
        ListNode01 fktt = kn.ReverseList(ln);
        System.out.println(fktt.val);
    }
    
    public ListNode01 ReverseList(ListNode01 head) {
        //先判断非法情况
        if(head == null){
            return head;
        }
        //用于保存前一个节点
        ListNode01 pre = null;
        //用于保存当前节点
        ListNode01 cur = head;
        while(cur != null){
            //①保存当前节点的下一个节点
            ListNode01 tmp = cur.next;
            //②把当前节点指向前一个节点
            cur.next = pre;
            //③把当前节点赋值给前一个节点
            pre = cur;
            //④把下一个节点赋值给当前节点
            cur = tmp;
        }
        return pre;
    }
}

class ListNode01 {
    int val;
    ListNode01 next;
    ListNode01(int val) {
        this.val = val;
    }
}

发表于 2019-02-26 20:06:47 回复(0)