反转链表

发表于 | 分类于 ，

反转链表

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
// 非递归
public static Node reverseUnRecur(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        Node cur = head;
        while (cur != null) {
            //记住当前节点的
            next.next = cur.next;
            // 当前节点指向前一个节点
            cur.next = pre;
            // 让pre记住当前节点
            pre = cur;
            // 当前节点后移
            cur = next;
        }
        return pre;
    }

    
    // 递归
    public static Node reverseRecur(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node next = head.next;
        head.next = null;
        Node revNode = reverseRecur(next);
        next.next = head;
        return revNode;
    }

    class Node {
        int val;
        Node next;
    }