首页 > 试题广场 > 反转链表
[编程题]反转链表
  • 热度指数:796420 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入一个链表,反转链表后,输出新链表的表头。
推荐
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 回复(50)
public static ListNode ReverseList(ListNode head) {//迭代
        ListNode pre = null;//pre为链表的前一个节点,初始,前一个节点肯定为空,null->first(head)->second->...->endth
        ListNode curr = head;//从head开始
        while (curr != null) {
            ListNode tmp = curr.next;//记录下一个节点的信息
            curr.next = pre;//将当前节点的指针指向前一个节点
            pre = curr;//把当前节点变成前一个节点
            curr = tmp;//把下一个节点变成当前节点
        }
        return pre;
 剑指offer的迭代解法,另一种递归的,时间太长未通过。
发表于 2020-05-27 19:15:08 回复(0)

import java.util.*;


public class Solution {
       public ListNode ReverseList(ListNode head) {

        Stack<ListNode> stack = new Stack<ListNode>();
        if(head==null)  return null;
           
        while(head!=null){
            stack.push(head);
            head = head.next;
        }
           

        ListNode out = null;
        ListNode current = null;
        out = current = stack.pop();
      
        ListNode new1 = null;
       
        
       while(stack.size()!=0){
           new1 = stack.pop();
           current.next = new1;
           current = current.next;
          }
        current.next = null;
        return out;
    }
    

}

编辑于 2020-05-12 08:49:01 回复(1)
1.迭代方法
public  ListNode ReverseList(ListNode head) {

        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

2. 递归方法
 public  ListNode ReverseList(ListNode head) {

        if (head == null || head.next == null) return head;
        ListNode p = ReverseList02(head.next);
        head.next.next = head;
        head.next = null;
        return p;

    }


发表于 2020-05-09 22:53:34 回复(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 || head.next == null){
            return head;
        }
        ListNode defaultHead = head;
        ListNode nextChange = head;
        ListNode realHead = head;
        /**
        *这个有一个算法,先取出头部的下一个数据,并且删除,如 1,2
        *这个时候获取真正的头部信息;3
        *将头部索引修改成我们取出来的1,2的信息;步骤4
        *并且将赋值之后的索引的next,换成之前的头部地址;将3赋值到5去;直到最开始的头部的next为空
        **/
        
        while(defaultHead.next != null){
            nextChange = defaultHead.next;//1
            defaultHead.next = nextChange.next;//2
            realHead = head;//3
            head = nextChange;//4
            head.next = realHead;//5
        }
        return head;
    }
}
发表于 2020-04-23 18:45:59 回复(0)
利用头插法特性,头插法后得到的链表与输入链表相反:
public class Solution {
    public ListNode ReverseList(ListNode head) {

        ListNode fakeHead = new ListNode(0);
        ListNode temp;
        while(head != null){
            temp = head.next;
            head.next = fakeHead.next;
            fakeHead.next = head;
            head = temp;
        }
        return fakeHead.next;
    }
}


发表于 2020-04-22 23:19:18 回复(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 newhead=null;
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
         ListNode next=cur.next;
        if(next==null){newhead=cur;}
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return newhead;
    }
}


发表于 2020-04-14 21:56:06 回复(0)
/*  这题的关键点要存下当前节点的前一个节点、当前点以及当前点后一个节点,以免出现节点丢失的问题。  在一开始可以把head当作当前点,null作为前一个点prenode,head.next作为后一个点aftnode  然后把当前点head指向prenode,此时head变化为新的prenode,aftnode变为新的head,  新的head.next变成aftnode,循环继续。  直到当前点的下下个节点为空,不能生成新的aftnode时,说明只剩最后两个点,逆序输出即可。  */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode prenode = null;
        ListNode aftnode = head.next;
        while(head.next.next != null){
            head.next = prenode;
            prenode = head; //当前节点保留作为下一个节点的前一个节点
            head = aftnode;   //当前节点后移
            aftnode = head.next; //保留下一个节点
        }
        head.next = prenode;
        aftnode.next = head;
        return aftnode;
    }
}


发表于 2020-04-08 16:23:06 回复(0)
三个指针p、q、r指向第一个、第二个、第三个(分别判断为空的情况),每次q.next指向p,然后前进替换,以r为结束标识。
public ListNode ReverseList(ListNode head) {
        if(head==null) return null;
        ListNode p=head;
        if(p.next==null) return p;
        ListNode q=p.next;
        p.next=null;
        if(q.next==null){
            q.next=p;
            return q;
        }
        ListNode r=q.next;
        while(r!=null){
            q.next=p;
            if(r.next==null) {
                r.next=q;
                break;
            }
            p=q;
            q=r;
            r=r.next;
        }
        return r;
    }

编辑于 2020-04-02 01:06:36 回复(0)
使用两个空节点pre和cur,cur作为head反转前的next,pre作为反转后的next;然后pre=head,head=cur;依次循环,返回pre作为反转后的头结点。
/*
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 pre=null;
        ListNode cur=null;
        while(head!=null){
            cur = head.next;
            head.next=pre;
            pre=head;
            head=cur;
        }
        return pre;
    }
}


发表于 2020-03-31 13:16:57 回复(0)

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode p = head;
        ListNode q = null;
        while(p != null) {
            ListNode curr = p.next;
            p.next = q;
            q =p;
            p = curr;
        }
        return q;
    }
}

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode currentNode, preNode, nextNode;
        currentNode = head;
        preNode = nextNode = null;
        while(currentNode != null){
            nextNode = currentNode.next;//保存后继结点
            currentNode.next = preNode;//让当前结点后继结点为前驱结点
            if(nextNode != null){//以当前结点设为前驱,保存的后继结点为下一个循环结点
                preNode = currentNode;
                currentNode = nextNode;
            }else{
                break;
            }
        }
        return currentNode;
    }
}

发表于 2020-03-22 17:43:05 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

发表于 2020-03-08 20:41:33 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
       if(head == null || head.next == null) {
           return head;
       }
        return recRev(head, head);
    }
   
    // 1->2->3
    // 2->1->3
    // 3->2->1; head表示新链表头;now是一直是原链表头
    public ListNode recRev(ListNode head, ListNode now) {
        if(now == null || now.next == null) {
            return head;
        }
        ListNode second = now.next;// 处理下一个节点
        ListNode third = second.next;
        now.next = third;
        second.next = head; // 更新头
        head = second;
        return recRev(head, now);
    }
}
发表于 2020-02-27 19:04:48 回复(0)
头插法建表:
public class ReverseList {
    public ListNode ReverseList(ListNode head) {
        if (head==null)
            return null;
        //头插法创建链表
        ListNode newList=null;
        ListNode temp;
        while (head!=null){
            //临时存储原链表的部分
            temp = head.next;
            //原链表的头接到新链表上
            head.next=newList;
            //更新新链表的头
            newList = head;
            //去掉原链表的头
            head=temp;
        }
        return newList;
    }
}


发表于 2020-02-20 11:39:25 回复(0)
public static ListNode ReverseList(ListNode head) {
        // 边界退出条件
        if(head == null || head.next == null){
            return head;
        }

        // 思路分析:1->2->3->4->5 拆分成 1->2 => 2->1 然后针对剩下3->4->5进行递归
        // 接着递归执行的结果得到的结点 5->4->3 再拼接当前 2->1 => 5->4->3->2->1
        ListNode post = head.next;
        head.next = null;
        if(post.next == null){
            // 只有2个结点
            post.next = head;
            return post;
        }else{
            // 结点数大于2
            // 先翻转前2个结点,得到post结点
            ListNode next = post.next;
            post.next = head;
            // 递归翻转post.next结点
            ListNode node = ReverseList(next);
            // 拼接递归得到的结点和post结点
            ListNode last = node;
            while (last.next != null){
                last = last.next;
            }
            last.next = post;
            return node;
        }
    }

发表于 2020-02-18 11:48:31 回复(0)
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //注意输入为null时的鲁棒性
        if(head == null){return null;}
        //pre 和 next 赋初值
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            //把下一个节点用next保存,防止断开,next相当于temp变量
            next = head.next;
            //head指向pre节点
            head.next = pre;
            //更新head和pre节点,相当于pre head从左向右移动
            //head为最后一个节点时,执行最后一轮循环,执行结束pre为最后一个节点,head为null
            //故返回的是pre
            pre = head;
            head = next;
        }
        return pre;
    }
}

发表于 2020-02-11 12:12:29 回复(0)
思路分析:
    1. 创建一个新的头节点。
    2. 遍历原始链表,每遍历一个节点,就创建一个与该节点值一样的对象。
    3. 将这个对象插入到新的头节点的后面。
    4. 遍历完后即得到了反转链表。
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 1. 创建一个新的头节点。值可以随便定义
        ListNode newHead = new ListNode (0);
        ListNode cur = head;
        ListNode temp = null;
        
        // 2. 遍历原始链表,每遍历一个节点,就创建一个与该节点值一样的对象。
        while (cur != null) {
            // 3. 将这个对象插入到新的头节点的后面。
            if (newHead.next == null) { // 新节点next为空则直接插入
                temp = new ListNode(cur.val);
                newHead.next = temp;
            } else {
                newHead.next = new ListNode(cur.val);
                newHead.next.next = temp;
                temp = newHead.next;
            }
            cur = cur.next;
        }
        // 4. 遍历完后即得到了反转链表。
        return newHead.next;
    }
}


发表于 2020-02-07 20:43:09 回复(0)
import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while (temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        for (int i = list.size()-1; i > 0; i--) {
            list.get(i).next=list.get(i-1);
        }
        list.get(0).next=null;
        return list.get(list.size()-1);
        
    }
}
为啥评论区的代码这么牛逼,都不需要导包,一个类也不用,我太菜了
发表于 2020-02-07 03:36:53 回复(0)
public static ListNode ReverseList(ListNode head) { if (head == null) return null;
    ListNode pre = null, p = head; while (p != null) {
        ListNode next = p.next;
        p.next = pre;
        pre = p;
        p = next;
    } return pre;
}
发表于 2020-01-27 21:56:59 回复(0)
解题思路:
step1:定义两个节点pre和cur,cur是pre的后继节点,如果是首次定义,需要把pre指向cur的指针去掉,避免形成环。

step2:后面的链表翻转,就是将cur指向pre,pre = cur , cur = cur.next

 public ListNode ReverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode pre,cur;
        pre = head;
        cur = pre.next;
        //pre是第一个节点,避免形成环
        pre.next = null;
       while(cur != null){
           //在 cur 指向 pre 之前一定要先保留 cur 的后继结点
          ListNode temp = cur.next;          
           cur.next = pre;
           pre = cur;
           cur = temp;
       }
        return pre;
    }

发表于 2020-01-23 10:31:57 回复(0)