206. Reverse Linked List 翻转单链表-详解

题目

答案一

public ListNode reverseList(ListNode head) {
    /* iterative solution */
    ListNode newHead = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

public ListNode reverseList(ListNode head) {
    /* recursive solution */
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode newHead) {
    if (head == null)
        return newHead;
    ListNode next = head.next;
    head.next = newHead;
    return reverseListInt(next, head);
}

答案二

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = new ListNode(0);
        new_head -> next = head;
        ListNode* pre = new_head;
        ListNode* cur = head; 
        while (cur && cur -> next) {
            ListNode* temp = pre -> next;
            pre -> next = cur -> next;
            cur -> next = cur -> next -> next; 
            pre -> next -> next = temp;
        }
        return new_head -> next;
    }
};

作图详解

设想有两个链表:

最主要的是：

1. 右边头指针的next指向左边的第一个
2. 但在指向之前应该先保存现有的指向
3. 指向左边第一个之后，然后恢复左边的指针重新纸箱第一个元素
4. 右边指针指向之前保存的指针

参考

In-place iterative and recursive Java solution 8ms C++ Iterative and Recursive Solutions with Explanations