206. Reverse Linked List

yPhantom 2019年10月14日 28次浏览

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

用递归和迭代两种方式实现链表反转。

迭代比较简单

class Solution {

    public ListNode reverseList(ListNode head) {
        ListNode preHead = null;
        while (head != null) {
            ListNode recordNext = head.next;
            head.next = preHead;
            preHead = head;
            head = recordNext;
        }
        return preHead;
    }
}

递归:

class Solution {

    public ListNode reverseList(ListNode head) {
        return doReverse(null , head);
    }

    private ListNode doReverse(ListNode pre, ListNode cur) {
        if (cur == null) {
            return pre;
        }
        ListNode recordNext = cur.next;
        cur.next = pre;
        return doReverse(cur, recordNext);
    }
}