链表——反转链表

剑指 Offer 24. 反转链表

题目链接

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000
1

借助外部空间（栈）

思路：

这种方式最容易想到实现，两次遍历链表，第一次遍历将链表所有节点push到栈中，第二次遍历，将栈中节点pop弹出，接到新的头节点后面即可。

栈也可有两种用法，第一种直接存节点元素val，然后第二次遍历时，需要每次创建一个节点将val设置进去。

代码实现：

 public ListNode reverseList(ListNode head) {
        //头节点为空或者只有一个节点直接返回
        if (head == null || head.next == null) {
            return head;
        }
         //头节点不动，自定义指针遍历链表
         ListNode cur = head;
         //借助栈 栈存放节点val值
         Stack<Integer> stack = new Stack<>();
         while (cur != null) {
             stack.push(cur.val);
             cur = cur.next;
         }

         ListNode newHead = new ListNode(-1);
         cur = newHead;
         while (!stack.isEmpty()) {
             cur.next = new ListNode(stack.pop());
             cur = cur.next;
         }
         return newHead.next;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

栈也可以直接存放节点元素，过程与上面类似，只不过要注意一点，链表尾节点next为null，由于原本头节点next指向下一个节点，而链表反转后此时的头节点成为了尾节点需要将next置为null。

代码如下：

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        //此时栈存放每个节点元素
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        ListNode newHead = new ListNode(-1);
        cur = newHead;
        while (!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next;
        }
        //反转过后的尾节点为原先的头节点
        //需要将尾节点next置为null
        cur.next = null;
        return newHead.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(n)，但是循环了两次；空间复杂度：O(n)【栈空间】

头插法

思路：

双指针头插法：一个指针用来遍历原链表，另一个指针用来将前面遍历得到的每一个节点进行头插至新链表，并且该指针不断往前移动，遍历结束返回后者指针即可。

代码实现：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        //该指针用来顺序遍历原链表
        ListNode cur = head;
        //刚开始的尾指针，指针不断向前移动
        ListNode prev = null;
        ListNode next;
        //头插法
        while (cur != null) {
            //记录当前节点的下一个节点 cur当前节点
            next = cur.next;
            //头插法
            cur.next = prev;
            //指针不断向前移动
            prev = cur;
            cur = next;
        }
        return prev;
    
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

遍历一次链表，时间复杂度：O(n)；没有借助额外空间, 空间复杂度：O(1)

递归解法

比较不好理解，而且空间复杂度还更大。（不做实现）

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为n层。

详细见递归解法，幻灯片很形象。