当前位置:网站首页>Algorithem_ ReverseLinkedList
Algorithem_ ReverseLinkedList
2022-04-23 15:54:00 【Mokong 9081】
Given the head of a singly linked list, reverse the list, and return the reversed list.
<!--more-->
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?
Solution 1
First of all followup, The most direct solution is , I put LinkNode Converted to an array , Then the array is in reverse order , Regenerate into new LinkNode
The code is as follows :
/**
* 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
}
var newNode = head
var nodeList: [Int] = []
while newNode != nil {
nodeList.append(newNode!.val)
newNode = newNode?.next
}
var resultNode = ListNode(nodeList[nodeList.count - 1])
var tempNode: ListNode?
for i in 0...nodeList.count - 2 {
let item = nodeList[nodeList.count - 2 - i]
let generateNode = generateNewNode(item)
if tempNode == nil {
resultNode.next = generateNode
}
else {
tempNode?.next = generateNode
}
tempNode = generateNode
}
return resultNode
}
func generateNewNode(_ val: Int) -> ListNode? {
return ListNode(val)
}
}
Solution 2
It's troublesome to understand here , May refer to ,Reverse a linked list, The video at the bottom of the page , Look at it several times. .
Iterative method :
- Declare three pointers ,prev = nil, current = head, next = nil,
- Loop traversal LinkedList
- change next front , First save next, Set up next = current.next
- Then change next, This step is reverse The key to , Set up current.next = prev
- then prev and current Move to the next node , Set up prev = current, current = next
The code is as follows :
/**
* 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 mutHead = head
if mutHead == nil || mutHead?.next == nil {
return mutHead
}
// initialize three pointers
// prev as NULL, curr as head, next as NULL
var prev: ListNode?
var curr = head
var next: ListNode?
// iterate through the link list, in the loop do the following
while (curr != nil) {
// Before changing next of current
// store the next node
next = curr?.next
// Now change next of current
// This is where revering happens
curr?.next = prev
// Move the prev and curr one step ahead
prev = curr
curr = next
}
return prev
}
}
Solution 3
The recursive method : A different understanding ,Reverse Linked List
The important thing is to change next Pointer to , Instead of assigning different values
- Declare two ListNode,prev and temp
- prev Used to represent the previous ,temp Represents temporarily stored , add mutHead Current , There are still three ListNode
- loop ,mutHead Not empty ,
- temp = mutHead, hold temp Assign to current
- mutHead = mutHead.next, hold mutHead Assign to the next
- temp.next = prev, hold temp Of next Point to prev, Note that this time temp The value of is current , That is, the current next is prev, The direction of the pointer is reversed
- prev = temp, hold prev The assignment is temp, namely prev Assign to current , Then continue the next traversal , know mutHead Empty stop
The code is as follows :
/**
* 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 mutHead = head
if mutHead == nil || mutHead?.next == nil {
return mutHead
}
var prev: ListNode?
var temp: ListNode?
while (mutHead != nil) {
temp = mutHead
mutHead = mutHead?.next
temp?.next = prev
prev = temp
}
return prev
}
}
Method four
The recursive method , Reference resources reclusive reverse linked list,
Mainly need to understand :
Each step of recursion is assigned a value curr.next.next = curr and curr.next = nil Two steps
/**
* 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 mutHead = head
if mutHead == nil || mutHead?.next == nil {
return mutHead
}
// recursive
let newHead = reverseList(mutHead?.next)
// The following code should be viewed separately
// mutHead?.next refer to mutHead Next ListNode
// mutHead?.next?.next refer to mutHead Next ListNode Of next Point to
// That's it reverse Point to
mutHead?.next?.next = mutHead
// And then put mutHead?.next namely mutHeead Of next Point to clear
mutHead?.next = nil
return newHead
}
}
版权声明
本文为[Mokong 9081]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231406039118.html
边栏推荐
- One brush 312 - simple repetition set - Sword finger offer 03 Duplicate number in array (E)
- WPS brand was upgraded to focus on China. The other two domestic software were banned from going abroad with a low profile
- Single architecture system re architecture
- Best practices of Apache APIs IX high availability configuration center based on tidb
- Go language, array, pointer, structure
- Why is IP direct connection prohibited in large-scale Internet
- MySQL - MySQL查询语句的执行过程
- 字符串最后一个单词的长度
- 【现代电子装联期末复习要点】
- CVPR 2022 quality paper sharing
猜你喜欢
腾讯Offer已拿,这99道算法高频面试题别漏了,80%都败在算法上
贫困的无网地区怎么有钱建设网络?
Spark 算子之coalesce与repartition
Function summary of drawing object arrangement in R language
API IX JWT auth plug-in has an error. Risk announcement of information disclosure in response (cve-2022-29266)
Ice -- source code analysis
C#,贝尔数(Bell Number)的计算方法与源程序
Temporal model: long-term and short-term memory network (LSTM)
The principle and common methods of multithreading and the difference between thread and runnable
Redis主从复制过程
随机推荐
gps北斗高精度卫星时间同步系统应用案例
Coalesce and repartition of spark operators
Upgrade MySQL 5.1 to 5.69
[self entertainment] construction notes week 2
Import address table analysis (calculated according to the library file name: number of imported functions, function serial number and function name)
一刷312-简单重复set-剑指 Offer 03. 数组中重复的数字(e)
s16.基于镜像仓库一键安装containerd脚本
GRBL学习(二)
R语言中绘制ROC曲线方法二:pROC包
一刷314-剑指 Offer 09. 用两个栈实现队列(e)
基于 TiDB 的 Apache APISIX 高可用配置中心的最佳实践
How can poor areas without networks have money to build networks?
【第5节 if和for】
Named in pytoch_ parameters、named_ children、named_ Modules function
String sorting
Config learning notes component
shell_ two
[section 5 if and for]
Pgpool II 4.3 Chinese Manual - introductory tutorial
实现缺省页面