328

206. Reverse Linked List (Easy)

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

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

Companies:
Microsoft, Bloomberg, Amazon, Facebook, Apple, Nvidia, Google, Yandex, Adobe, eBay, IBM

Related Topics:
Linked List, Recursion

Similar Questions:

• Reverse Linked List II (Medium)
• Binary Tree Upside Down (Medium)
• Palindrome Linked List (Easy)
• Reverse Nodes in Even Length Groups (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/odd-even-linked-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode evenHead, *evenTail = &evenHead, oddHead, *oddTail = &oddHead;
        for (bool odd = true; head; odd = !odd, head = head->next) {
            if (odd) {
                oddTail->next = head;
                oddTail = head;
            } else {
                evenTail->next = head;
                evenTail = head;
            }
        }
        oddTail->next = evenHead.next;
        evenTail->next = NULL;
        return oddHead.next;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/odd-even-linked-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *odd = head, *even = head->next, *evenHead = even; 
        while (even && even->next) {
            odd->next = even->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};