题目概述

反转链表

题目解答

迭代解法

  1. 3和4 ：反转节点
  2. 1、2: 后移旧头节点
1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode reverseList(ListNode head) {

    ListNode newHead = null;
    while(head != null){
        ListNode tmp = head.next; // 1

        head.next = newHead; // 3
        newHead = head;      // 4

        head = tmp; // 2 后移head节点
    }
    return newHead;
}

在迭代解法的基础上可以衍生出其递归解法

  1. 结束条件是：当头节点遍历到末尾，且为空时，返回newHead
  2. 1、2步是遍历所有节点操作
  3. 3、4步是将head.next指向前一个节点（newHead），并将newHead后移一位（newHead = head; ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseList(head, null);
    }

    public ListNode reverseList(ListNode head, ListNode newHead) {

        if (head == null) {
            return newHead;
        }

        ListNode tmp = head.next;          // 1

        head.next = newHead;               // 3
        newHead = head;  									 // 4

        return reverseList(tmp, newHead);  // 2
    }
}

在此基础上可以解决面试题 02.06. 回文链表