首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Algorithem_ReverseLinkedList

Algorithem_ReverseLinkedList

原创
作者头像
莫空9081
发布2022-04-23 12:55:50
1780
发布2022-04-23 12:55:50
举报
文章被收录于专栏:iOS 备忘录iOS 备忘录

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:

image1
image1
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

image2
image2
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?

解法一

先撇开 followup,最直接的解法时,我把 LinkNode 转为数组,然后数组逆序,再生成新的 LinkNode

代码如下:

/**
 * 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)
    }
}

解法二

这里理解比较麻烦,可参考,Reverse a linked list,页面最下方的视频,多看几遍。

迭代解法:

  1. 声明三个指针,prev = nil, current = head, next = nil,
  2. 循环遍历LinkedList
    1. 改变 next 前,先保存 next,设置 next = current.next
    2. 然后改变 next,这一步是 reverse 的关键,设置 current.next = prev
    3. 然后 prev 和 current 向下个节点移动,设置 prev = current, current = next

代码如下:

/**
 * 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
    }
}

解法三

递归解法:另一种不同的理解,Reverse Linked List

重要是改变next指针指向,而不是赋不同的值

  1. 声明两个ListNode,prev 和 temp
  2. prev 用于代表前一个,temp 代表暂时存储的,加上 mutHead 当前的,一共还是三个 ListNode
  3. 循环,mutHead 不为空,
    1. temp = mutHead,把 temp赋值为当前
    2. mutHead = mutHead.next,把 mutHead赋值为下一个
    3. temp.next = prev,把 temp 的 next 指向 prev,注意此时 temp 的值是当前,即当前的下一个是 prev,指针的方向就实现了反过来了
    4. prev = temp,把 prev 赋值为 temp,即 prev 赋值为当前,然后继续下一次遍历,知道 mutHead 为空停止

代码如下:

/**
 * 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
    }
    
}

解法四

递归解法,参考 reclusive reverse linked list

主要需要理解:

递归中每一步赋值 curr.next.next = curr 和 curr.next = nil 两步

/**
 * 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
        }
        
        // 递归
        let newHead = reverseList(mutHead?.next)
        
        // 下面代码要分开看
        // mutHead?.next指的是 mutHead 的下一个 ListNode
        // mutHead?.next?.next指的是 mutHead 的下一个 ListNode 的 next 指向
        // 这样就完成了 reverse指向
        mutHead?.next?.next = mutHead
        // 然后把 mutHead?.next 即 mutHeead 的 next 指向清除
        mutHead?.next = nil

        return newHead
    }
}

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解法一
  • 解法二
  • 解法三
  • 解法四
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档