反转链表-蒲公英云

反转链表

题目描述

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

链表的数据结构如下：

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

[反转链表]也叫做[链表逆置].比如一个链表是这样的：1->2->3->4->5，通过反转后可以变成为5->4->3->2->1。

容易想到的方法遍历一遍链表，利用三个指针，第一个指针P存储反转的节点，第二个指针q存储当前的节点，反转前p—>q，反转后q—>p,第三个指针temp存储q节点的下一个节点用于遍历。代码如下：

第一种方法遍历求解反转链表问题：

public class Solution {
    public static void main(String[] args) {
        //构造树结构测试用
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        System.out.print("BeforeReverse: ");
        visit(a);
        System.out.println();
        Long begintime = System.nanoTime();
        ListNode f = ReverseList(a);
        Long endtime = System.nanoTime();
        System.out.print("AfterReverse: ");
        visit(f);
        System.out.println();
        System.out.print("ReverseTime = "+(endtime - begintime)+"ns");
    }
    public static void visit(ListNode p) {
        while(p!=null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
    }
    public static ListNode ReverseList(ListNode head) {
            ListNode p = null;
            ListNode q = head;
            ListNode temp = null;
            while(q!=null){
               temp = q.next;
               q.next = p;
               p = q;
               q = temp;
            }
          return p;
        }
}

程序运行的结果：

遍历求解反转链表的时间复杂度为O(n)。

这个问题也可以使用递归求解。只需要修改ReverseList( )里面的内容就可以，其他的地方不用变。

第二种方法递归求解反转链表问题：

public static ListNode ReverseList(ListNode head) {
        //如果链表为空或者链表中只有一个元素
        if(head == null || head.next == null)
        {
            return head;
        }
        else
        {
            //先反转后面的链表，走到链表的末端结点
            ListNode newhead = ReverseList(head.next);
            //再将当前节点设置为后面节点的后续节点
            head.next.next = head;
            head.next = null;
            return newhead;
        }
    }