LeetCode 206. Reverse Linked List

LeetCode 206. Reverse Linked List

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

Matter

You are given the head of a singly linked list.

Reverse the direction of the list so that all links point backward, and return the new head.

Example.

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

Output:
[5,4,3,2,1]

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

Output:
[2,1]

[3]
Input:
head = []

Output:
[]

Constraints

0 <= number of nodes <= 5000

-$5000$ <= Node.val <= $5000$

Problem analysis

The core of this problem is changing the direction of each node’s pointer.

In a singly linked list:

current -> next

Solution

Rearrange

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pNodeResult = nullptr;

        do
        {
            std::vector<int> vctData;

            while(true)
            {
                if(!head)
                    break;

                vctData.push_back(head->val);
                head = head->next;
            }

            if(!vctData.size())
                break;

            int i32Size = (int)vctData.size();

            ListNode* pList = new ListNode;
            ListNode* pListStart = pList;

            for(int i = 0; i < i32Size-1; ++i)
            {
                pList->val = vctData[i32Size-1-i];
                pList->next = new ListNode;
                pList = pList->next;
            }

            pList->val = vctData[0];
            pList->next = nullptr;

            pNodeResult = pListStart;
        }
        while (false);
        
        return pNodeResult;
    }
};

Reuse

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* pListPrev = nullptr;
        ListNode* pListCur = head;

        while(true)
        {
            if(!pListCur)
                break;

            ListNode* pListNew = pListCur->next;
            pListCur->next = pListPrev;
            pListPrev = pListCur;
            pListCur = pListNew;
        }

        return pListPrev;
    }
};