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
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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
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
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
let [prev, current] = [null, head];
while (current) {
[current.next, prev, current] = [prev, current, current.next];
}
return prev;
};
Recursive
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
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
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
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
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
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
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution
{
/**
* @param ListNode $head
* @return ListNode
*/
function reverseList($head)
{
$prev = null;
$current = $head;
while (!is_null($current)) {
$next = $current->next;
$current->next = $prev;
$prev = $current;
$current = $next;
}
return $prev;
}
}
Recursive
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution
{
/**
* @param ListNode $head
* @return ListNode
*/
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
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
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
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
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
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
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
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
}
}