題目敘述
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?
題目翻譯
題目很間單的要求，就是將整個連結序列反轉。嘗試看是否能分別寫出迭代和遞迴的解法。
解法解析
這題很簡單，做法就是直接去遍歷所有的節點。只是遍歷的方式可以用迭代或是遞迴的方式來處理。覺得比較需要提到的是遞迴的地方，因為是要反轉，所以原本是 1 -> 2 -> 3 要變成 3 -> 2 -> 1。所以寫法中的要注意 head.next.next = head。
解法範例
Go
Iterative
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
Recursive
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
p := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return p
}
JavaScript
Iterative
var reverseList = function (head) {
let [prev, current] = [null, head];
while (current) {
[current.next, prev, current] = [prev, current, current.next];
}
return prev;
};
Recursive
var reverseList = function (head) {
if (!head || !head.next) {
return head;
}
const p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
};
Kotlin
Iterative
class Solution {
fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var current: ListNode? = head
while (current != null) {
val next = current.next
current.next = prev
prev = current
current = next
}
return prev
}
}
Recursive
class Solution {
fun reverseList(head: ListNode?): ListNode? {
if (head == null || head?.next == null) return head
var p: ListNode? = reverseList(head?.next)
head?.next?.next = head
head?.next = null
return p
}
}
PHP
Iterative
class Solution
{
function reverseList($head)
{
$prev = null;
$current = $head;
while (!is_null($current)) {
$next = $current->next;
$current->next = $prev;
$prev = $current;
$current = $next;
}
return $prev;
}
}
Recursive
class Solution
{
function reverseList($head)
{
if (is_null($head) || is_null($head->next)) {
return $head;
}
$p = $this->reverseList($head->next);
$head->next->next = $head;
$head->next = null;
return $p;
}
}
Python
Iterative
class Solution:
def reverseList(self, head: ListNode | None) -> ListNode | None:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
Recursive
class Solution:
def reverseList(self, head: ListNode | None) -> ListNode | None:
if (not head) or (not head.next):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
Rust
Swift
Iterative
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
var prev: ListNode? = nil
var curr: ListNode? = head
while curr != nil {
let next = curr?.next
curr?.next = prev
prev = curr
curr = next
}
return prev
}
}
Recursive
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
let p: ListNode? = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return p
}
}