Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

Reverse a singly linked list.

Thoughts

1. 对Linked list翻转最简单方法就是把next指向prior.

2. 循环内部需要一个back_next从而使得node能跳转到下一个需要翻转的

3. 为了最后一个node的next成功翻转，判断条件不该再有node->next != NULL. 最后node是NULL, 因此需要返回prior.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prior = NULL, *node = head;
        while (node != NULL) {
            auto next = node->next;
            node->next = prior;
            prior = node;
            node = next;
        }
        return prior;
    }
};

/**
 * 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 node = head;
        if (node == null || node.next == null) {
            return node;
        }
        ListNode next = node.next;
        while (node != null && next != null) {
            ListNode newNext = next.next;
            next.next = node;
            node = next;
            next = newNext;
        }

        head.next = null;
        return node;
    }

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

        return prior;
    }

}

Analysis

做题耗时: 17 min

Errors:

1. 没有用newNext存下下个next，只用了next导致被覆盖

时间复杂度O(n), 空间复杂度O(1)