反转链表

浅浅的花香味﹌ 2022-05-13 22:45 297阅读 0赞

## 题目描述 ##

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

链表的数据结构如下：

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;
            }
    
    }

程序运行的结果：

![70][]

遍历求解反转链表的时间复杂度为**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;
            }
        }

在这里使用递归实现链表的反转是非常巧妙的一种解法，它利用递归走到链表的末端，然后再更新每一个node的next 值 ，实现链表的反转。

这里还是以链表：1->2->3->4->5为例。第一次走到末端时head指向4。

第一步：newhead走向链表的结尾，指向的是链表的最后一个节点，此时head.val = 4，newhead.val = 5；

第二步：head.val = 4，head.next.val = 5，head.next.next = head就实现了链表的反转，把4-->5变为5-->4。

第二步： head.next = null，就是把节点4的下一个节点指向null。

一个节点处理完了再通过递归回溯，此时的head指向的节点的值变成了3。

第一步：newhead就是head的下一个节点，此时head.val = 3，newhead.val = 4；

第二步：head.val = 3，head.next.val = 4，head.next.next = head就实现了链表的反转，把3-->4变为4-->3。

第二步： head.next = null，就是把节点3的下一个节点指向null。

依次类推。到反转的最后一个节点它的下一个节点的值因为设置了 head.next = null语句，可以把它的next指向空。所以整个逻辑是没有问题的。

程序运行结果：

![70 1][]