source: https://leetcode.com/problems/reverse-linked-list
C/C++ Solution to LeetCode problem 206. Reverse Linked List.
Problem
Given the head
of a singly linked list, reverse the list, and return the reversed list.
Examples
Example 1:
Input: [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
Solution
We just need to point each node to the previous node instead of the next one, and the last node becomes the head.
Two solutions, one using a while
loop and the other recursive
.
Solution 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* p = nullptr;
ListNode* c = head;
while (c) {
ListNode* n = c->next;
c->next = p;
p = c;
c = n;
}
return p;
}
};
Solution 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return head;
ListNode* tmpHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return tmpHead;
}
};