首页 > 试题广场 > 反转链表
[编程题]反转链表
输入一个链表,反转链表后,输出新链表的表头。
推荐
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 回复(41)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
                return null;
            }
        ListNode p = null;
        ListNode s = null;
        while(head != null){
            s = head.next;
            head.next = p;
            p = head;
            head = s;
        }
        return p;
    }
}
p代表head要逆转的前一个结点
s代表head要逆转的后一个节点,在逆转结点之前,s用来保存未逆转的链表,防止丢失
发表于 2019-07-21 11:57:19 回复(0)
新建一个链表头插法,我觉得我这个也不错,嘿嘿
public static ListNode ReverseList(ListNode head) {
    ListNode newHead = null;  while (head != null) {
      if (newHead == null) {
            newHead = new ListNode(head.val);
        } else {
            ListNode node = new ListNode(head.val);
            node.next = newHead;
            newHead = node;
        }
        head = head.next;
    } return newHead;
}

编辑于 2019-07-18 11:44:26 回复(0)
递归方法解决:
在本题中,我了解到判断条件的变化
需要注意两点:
1.要清晰明确头结点的存储位置
2.要注意设置空值,避免链表成环状

思路:假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表
如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转后链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给head->next->next指针,并且一定要记得让head->next =NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层head->next->next赋值的时候会覆盖后续的值。
/*
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||head.next == null)
          return head;
        //先反转后面的链表,走到链表的末端结点
        ListNode ReverseNode=ReverseList(head.next); 
        //再将当前节点设置为后面节点(新的头结点)的后续节点
        head.next.next=head;
        head.next=null;

        return ReverseNode;
    }
}
发表于 2019-07-14 11:06:38 回复(0)
    /**
     * 反转链表
     * @param head
     * @return */
    public static ListNode ReverseList(ListNode head){
        if (head==null){
            return null;
        }
        ListNode cur = head;
        ListNode q = null;//反转之后的链表头
        while (cur!=null){
            ListNode p = cur;//待反转的结点
            cur = cur.next;
            p.next = q;//将结点指向头结点并将头更新
            q = p;
        }
        return q;
    }

编辑于 2019-07-12 16:37:43 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pNode = head;
        ListNode pPrev = null;
        ListNode ReverseListNode = null;
        while(pNode!=null){
            ListNode pNext = pNode.next;
            if(pNext == null) ReverseListNode = pNode;
            pNode.next = pPrev;//修改pNode的指针域指向pPre,即将上一个节点的地址赋值给pNode的指针
            pPrev = pNode;//将pNode结点赋值给pPre
            pNode = pNext;//将pNode的下一个结点赋值给pNode,每次反转指针是在pNode与pPrev结点之间,反转结束后,这两个指针前移
        }
        return ReverseListNode;
    }
}

发表于 2019-07-11 16:23:02 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode res = new ListNode(0);
        ListNode run = new ListNode(0);
        run = head;
        while(run != null){
            ListNode next = run.next;//头插法
            run.next = res.next;
            res.next = run;
            run = next;
        }
        return res.next;
    }
}

发表于 2019-07-08 17:50:20 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
     
        ListNode cur = head;
        ListNode newHead =null;
        ListNode next;
        while(cur!=null){
            //保存当前节点的下一个节点
            next = cur.next;
            //当前节点的下一个节点设置在新链表的头部
            cur.next = newHead;
            //将当前链表赋值给新链表
            newHead = cur;
            //指针后移 指向下一个节点
            cur =next;          
        }
        return newHead;

    }
}

编辑于 2019-07-02 11:46:50 回复(0)
public static ListNode ReverseList(ListNode head) {
        // 没有节点或一个节点
        if (head == null || head.next == null) {
            return head;
        }
        ListNode preNode = head;
        ListNode node = head.next;
        // 两个节点及以上
        // 链表中有三个及以上节点才会进入此循环
        while (node.next != null) {
            if (preNode == head) { // 若preNode为head,将其next设为null
                preNode.next = null;
            }
            // 保存node的下一个节点,
            //因为反转preNode和node两个节点后,node与下一个节点会断开,遍历时会找不到下一个节点
            ListNode nextNode = node.next;
            node.next = preNode; // 反转两个节点
            preNode = node; // preNode后移
            node = nextNode; // node后移
        }
        // 循环结束,只剩最后一个节点node和倒数第二个节点preNode,并且两节点断开
        // 若链表只有两个节点,不进入上述循环,直接执行下面语句
        node.next = preNode; // 将最后两个节点反转
        return node; // 返回最后一个节点node,即新的头结点
    }
发表于 2019-06-30 13:45:00 回复(0)
/*
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) {
        if(head == null) return null;
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while(temp.next != null){
            stack.push(temp);
            temp = temp.next;
        }
        ListNode res = temp;
        if(!stack.isEmpty()){
            res.next = stack.peek();
        }else{
            res.next = null;
        }
        while(!stack.isEmpty()){
            temp.next = stack.pop();
                temp = temp.next;
        }
        temp.next = null;
        return res;
    }
}
用栈来做
发表于 2019-06-26 22:24:54 回复(0)
        ListNode prev = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = prev;
            prev = head;
            head = tmp;
        }
        return prev;
编辑于 2019-06-13 16:29:18 回复(0)
/*
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) {
        
        if(head == null || head.next == null)
            return head;
        Stack<ListNode> stack = new Stack<ListNode> ();
        ListNode node = head;
        while(node != null)
        {
            stack.push(node);
            node = node.next;
        }
        
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(!stack.isEmpty())
        {
            cur.next = stack.pop();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;

    }
}

/*
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) {
        
        if(head == null || head.next == null)
            return head;
        
        //ListNode dummy = new ListNode(0);
        //dummy.next = head;
        
        ListNode pre = null;
        ListNode cur = head;
        ListNode fol = null;
        
        while(cur != null)
        {
            fol = cur.next;
            cur.next = pre;
            pre = cur;
            cur = fol;
        }
        return pre;
    }
}


发表于 2019-06-10 23:59:30 回复(0)
此题链表的头部不是空节点,即head.val是有值的;
解题方法为重新构造一个链表,ListNode newHead=new ListNode(0),然后遍历原始链表将每一个节点插入新链表的头部,即
~~~
ListNode temp=current.next;
current.next=newHead.next;
// 头部插入
newHead.next=current;
current=temp;
~~~
最后,由于头结点是空节点,所有返回头结点的下一个节点就行newHead.next。
编辑于 2019-06-04 21:30:48 回复(0)
使用头插法反转链表 
 public ListNode ReverseList(ListNode head) {
        // 使用头***r />         ListNode p = head;
         
        if(head==null || head.next==null){
            return head;
        }
        ListNode q = head.next;
        head.next = null;
        while(q!=null){
            p=q;
            q=q.next;
            p.next=head;
            head=p;
        }
        return head;
    }
发表于 2019-05-30 20:57:18 回复(0)
    public ListNode ReverseList(ListNode head) {
        //this is an operation between three node
        ListNode p = head;
        ListNode next =null;
        ListNode pre = null;
                 if(p != null){             while(p.next!=null){                 //1. split between p and p.next                 next = p.next;                 p.next = null;                 //2. reverse                  p.next = pre;                 //3. change position                 pre = p;                 p = next;             }                          p.next = pre;
                     }

        return p;
    }
编辑于 2019-05-30 16:54:11 回复(0)
    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)