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

143个回答

添加回答
推荐
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 回复(39)

Solution 1 用头插法解决(推荐)

// 将链表分为已反转部分和待反转部分,用三个指针分别指向已反转部分链表头、链表尾以及未反转部分链表头
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next ==null){
            // 考虑没有节点,或者只有一个节点的情况
            return head;
        }
        // 此时至少有两个节点
        ListNode tempHead = head;        //头插法 已反转部分的链表头,结束时需放到全部已反转链表的尾部
        ListNode tempTail = head.next;        // 头插法已反转部分的链表尾部
        while(tempTail.next != null){          // 判断是否还有新节点需要插入
            ListNode newNode = tempTail.next;
            tempTail.next = newNode.next;        //记录剩余未反转部分的节点
            // 头插法
            newNode.next = tempHead.next;
            tempHead.next = newNode;
        }
        // 最后把临时表头节点放到全部已反转链表的尾部
        head = tempHead.next;        //已反转部分新表头
        tempTail.next = tempHead;
        tempHead.next = null;

        return head;

    }
}

Solution 2 用栈解决(简单)

import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next ==null){
            return head;
        }
        Stack stack = new Stack();
        ListNode getValueToStack = head;
        while(getValueToStack != null){
            stack.push(getValueToStack.val);
            getValueToStack = getValueToStack.next;
        }
        ListNode getStackValueToList = head;
        while(!stack.isEmpty()){
            getStackValueToList.val = stack.pop();
            getStackValueToList = getStackValueToList.next;
        }
        return head;

    }
}
发表于 2019-03-18 10:36:49 回复(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)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 头插法
        ListNode h = new ListNode(666);
        while(head != null){
            ListNode p = head.next;
            head.next = h.next;
            h.next = head;
            head = p;
        }
        return h.next;
    }
}


发表于 2019-02-12 18:12:05 回复(0)
public class Solution {
    
    public ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        ListNode newNode = null;
        //用一个next来存head的next
        ListNode next = null;
        while(head != null){
            next = head.next ;
            //向第一个插入 变成第一个
            head.next = newNode;
            //改变头
            newNode = head;
            //head进入下一个
            head = next;
            
        }
        return  newNode;
    }
}


发表于 2019-01-27 15:50:06 回复(0)



public static ListNode ReverseList(ListNode head) {  if (head == null) { return head;  }
    ListNode result = new ListNode(head.val);  while (head.next != null) {
        ListNode temp = new ListNode(head.next.val);   temp.next = result;  head = head.next;  result = temp;  }  return result; }


编辑于 2019-01-24 15:23:24 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
          ListNode pre = null;
          ListNode curr = head;
          while(curr!=null) {          
             ListNode temp  = curr.next;
             curr.next = pre;
             pre = curr;
             curr =temp;
          }
          return pre;
    }
}

发表于 2019-01-13 14:30:26 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode f = head;
        ListNode b = head;
        ListNode t = head.next;
        head.next = null;
        while(f != null){
            f = t.next;
            t.next = b;
            b = t;
            t = f;
        }
        return b;
    }
}

编辑于 2019-01-10 15:08:10 回复(0)
public static ListNode ReverseList(ListNode head) { if (head==null){ return null;
    }
    ListNode i=head,j=head.next,h;
    i.next=null; while (j!=null){ //先保存j的next  h=j.next;
        j.next=i;
        i=j;
        j=h;
     } return i;
}

发表于 2018-12-25 22:05:14 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
      if(head==null||head.next==null)return head;
         ListNode p=head,post,pre=null;//pre<--p<--post
        while(p!=null){
            post=p.next;
            p.next=pre;
            pre=p;
            p=post;
        }
       return pre;
    }
}

编辑于 2018-12-24 20:08:01 回复(1)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

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

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号