反转链表

发表于 分类于 阅读次数：

题目

本题为leetcode206号题目

反转一个单链表

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路

这里提供两个思路。

方法一：

一次反转

方法二：请看实现部分的注释
偷懒了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public static class ListNode {
        public int value;
        public ListNode next;

        public ListNode(int data) {
            this.value = data;
        }
}

//方法一
public ListNode reverseList1(ListNode node) {

        ListNode prev = null;
        ListNode next = null;
        while(node != null) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }

public ListNode reverseList2(ListNode node) {
        
        if(node == null || node.next == null) {
            return node;
        }
        
    
        ListNode nextNode = node.next;//保存下一个节点
        //等递归到底，不要动他。然后把最尾部的元素带回来作为返回值
        ListNode ret = reverseList(nextNode);
        //此处应该换成node.next.next = node也没问题;
        nextNode.next = node;//（反转）下一个节点的next指向当前节点
        node.next = null; //这一行是为了当前节点的下一个节点本来是nextNode，如果不设置为null的话，
        //就会形成nextNode.next -> node -> node.next ->nextNode这种循环了，会产生异常
        return ret;
    }

吐槽

这题是链表中的经典题目，在其他关于链表的题目中有广泛的应用，所以必须也是必然掌握。
注：我这个脑瘫写了几个钟都不太会，嘻嘻