206. Reverse Linked List
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
From: LeetCode
Link: 206. Reverse Linked List
Solution:
Ideas：
- Initialize three pointers: prev (initially NULL), curr (pointing to the head of the list), and next (initially NULL).
- Iterate through the list. In each iteration:
- Store the next node in next.
- Reverse the current node’s next pointer to point to prev.
- Move prev and curr one step forward.
- After the loop, prev will point to the new head of the reversed list.
- Update head to prev and return it.
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *prev = NULL;
struct ListNode *curr = head;
struct ListNode *next = NULL;
while (curr != NULL) {
next = curr->next; // Store next node
curr->next = prev; // Reverse current node's pointer
prev = curr; // Move pointers one position ahead
curr = next;
}
head = prev; // Update head to new first node
return head;
}
