剑指 Offer 24. 反转链表

206. 反转链表

题目描述

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

输入输出

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

基本思路

双指针法

举例第一次循环：

  1. cur -> 1 pre -> null即结尾空指针
  2. tmp -> 2 1 -> null pre -> 1cur -> 2
  3. 第一次循环结束 1与2之间断开 1连接结尾空指针

时间O(n) 空间O(1)

递归法

  1. reverseList到4的时候停止 此时head=4
  2. 4的next(即5)的next(即4和5之间的指针)指向4 此处转向
  3. 走到最后1节点指向null

时间O(n) 空间O(n)

java实现

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

//双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

//递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}