

Jonathan's Studio

Jonathan's Studio

算法基础（四）链表综合



算法基础（四）链表综合

实习准备

字数统计: 2.2k阅读时长: 11 min

 2020/08/29   Share

• 
• 
• 
• 
• 

算法基础（四）链表综合

//单链表节点结构
class ListNode: Equatable {
    static func == (lhs: ListNode, rhs: ListNode) -> Bool {
        if Unmanaged.passUnretained(lhs as AnyObject).toOpaque() == Unmanaged.passUnretained(rhs as AnyObject).toOpaque() {
            return true
        } else {
            return false
        }
    }
    
    var value: Int
    var next: ListNode?
    
    init(_ value: Int) {
        self.value = value
        self.next = nil
    }
}

//双链表节点结构
class DoubleNode {
    var value : Int
    var previous :DoubleNode?
    var next:DoubleNode?
    
    init(_ value :Int) {
        self.value = value
        self.previous = nil
        self.next = nil
    }
}

class List {
    private(set) var head: ListNode?
    
    init(_ head: inout ListNode) {
        self.head = head
        if checkCycle() {
            fatalError("List is a cycle.")
        }
    }
    //尾插法
    func appendToTail(_ value: Int) {
        guard head != nil else {
            head = ListNode.init(value)
            return
        }
        var node: ListNode? = head
        while (node?.next != nil) {
            node = node?.next
        }
        node?.next = ListNode(value)
    }
    
    //头插法
    func appendToHead(_ value: Int) {
        let node = ListNode.init(value)
        node.next = head
        head = node
    }
    
    //指定位置后插法
    func append(_ value: Int, upTo index: Int) {
        guard index > 0 else {
            fatalError("index不能为负数和0.")
        }
        guard head != nil else {
            head = ListNode.init(value)
            return
        }
        var index = index
        var node: ListNode? = head
        while node?.next != nil && index > 1 {
            node = node?.next
            index -= 1
        }
        guard index == 1 else {
            fatalError("out of the range of the list.")
        }
        let temp = ListNode.init(value)
        temp.next = node?.next
        node?.next = temp
    }
    
    func removeListNode(at index: Int) {
        guard head != nil else {
            fatalError("链表为空.")
        }
        guard index > 1 else {
            if index == 1 {
                let node = head?.next
                head?.next = nil
                head = node
                return
            } else {
                fatalError("index不能为负数和0.")
            }
        }
        var index = index
        var node: ListNode? = head
        while node?.next != nil && index > 2 {
            node = node?.next
            index -= 1
        }
        guard node?.next != nil else {
            fatalError("out of the range of the list.")
        }
        //临时存储删除节点，最后要将它与next彻底断绝关系
        let temp = node?.next
        node?.next = temp?.next
        temp?.next = nil
    }
    
    //更改节点值
    func changeListNodeValue(_ value: Int, at index: Int) {
        guard head != nil else {
            fatalError("链表为空.")
        }
        guard index > 0 else {
            fatalError("index不能为负数和0.")
        }
        var index = index
        var node: ListNode? = head
        while node?.next != nil && index > 1 {
            node = node?.next
            index -= 1
        }
        guard index == 1 else {
            fatalError("out of the range of the list.")
        }
        node?.value = value
    }
    
    //节点交换
    func swapListNode(firstIndex fi: Int, secondIndex si: Int) {
        guard head != nil else {
            fatalError("链表为空.")
        }
        guard head?.next != nil else {
            fatalError("链表只有1个节点.")
        }
        guard fi > 0 && si > 0 else {
            fatalError("index不能为负数和0.")
        }
        guard fi != si else {
            return
        }
        let low = fi<si ? fi:si
        let high = fi>si ? fi:si
        //设置哑结点
        let node: ListNode? = ListNode.init(0)
        node?.next = head
        //低节点的左节点和高节点的左节点
        var llNode = node
        var hlNode = node
        for i in 1...high-1 {
            if low != 1 && i == low {
                llNode = hlNode
            }
            hlNode = hlNode?.next
        }
        guard hlNode?.next != nil else {
            fatalError("out of the range of the list.")
        }
        //低节点和高节点
        let lNode = llNode?.next
        let hNode = hlNode?.next
        //低节点右节点和高节点右节点
        let lrNode = lNode?.next
        let hrNode = hNode?.next
        //相邻情况
        if high-low == 1 {
            //头节点交换情况
            if low == 1 {
                head = hNode
                head?.next = lNode
                lNode?.next = hrNode
            } else {
                llNode?.next = hNode
                hNode?.next = lNode
                lNode?.next = hrNode
            }
        } else {
            //不相邻情况
            //头节点交换情况
            if low == 1 {
                head = hNode
                head?.next = lrNode
                hlNode?.next = lNode
                lNode?.next = hrNode
            } else {
                llNode?.next = hNode
                hNode?.next = lrNode
                hlNode?.next = lNode
                lNode?.next = hrNode
            }
        }
    }
    
    //链表倒置
    func invertList() {
        guard head != nil && head?.next != nil else {
            return
        }
        var node = head
        var nNode = head?.next
        var pNode: ListNode? = nil
        
        while nNode != nil {
            let temp = nNode?.next
            nNode?.next = node
            node?.next = pNode
            pNode = node
            node = nNode
            nNode = temp
        }
        head = node
    }
    
    //打印
    func getString() -> String {
        //设置哑节点
        var node: ListNode? = ListNode.init(0)
        node?.next = head
        var result = ""
        while (node?.next != nil) {
            node = node?.next
            if node?.next == nil {
                result +=  String(node!.value)
            } else {
                result +=  (String(node!.value) + ",")
            }
        }
        return result
    }
    
    //检测是否成环
    func checkCycle() -> Bool {
        //速度检测是否成环
        var slow: ListNode? = head
        var fast: ListNode? = head
        while fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            if slow == fast {
                return true
            }
        }
        return false
    }

}

var listNode = ListNode.init(0)
var listNode1 = ListNode.init(8)
listNode.next = .init(1)
listNode.next?.next = listNode1

let list = List(&listNode)
list.appendToHead(4)
list.appendToTail(5)
print(list.getString())
list.appendToHead(56)
print(list.getString())

list.append(99, upTo: 6)
print(list.getString())

list.removeListNode(at: 1)
print(list.getString())

list.head?.next?.next?.value

list.changeListNodeValue(88, at: 3)
print(list.getString())

list.swapListNode(firstIndex: 4, secondIndex: 6)
print(list.getString())
list.invertList()
print(list.getString())

var a = ListNode.init(2)
let lista = List.init(&a)
lista.removeListNode(at: 1)
print(lista.getString())
lista.append(22, upTo: 3)
print(lista.getString())
lista.appendToTail(33)
print(lista.getString())
lista.swapListNode(firstIndex: 1, secondIndex: 2)
print(lista.getString())
lista.invertList()
print(lista.getString())


//忽略成环问题
class Solution {
    /**
     给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
     将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
     给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
     
     思路：
        先找出中点（快慢指针只需n/2次）
        拆分为两个链
     
         表：
            右链表反转操作（n/2-1）
            两链表穿插操作（n/2）
     */
    func reorderList(_ head: ListNode?) {
        guard let head = head else {
            return
        }
        guard head.next != nil && head.next?.next != nil else {
            return
        }
        //快慢指针获取中点右节点
        var node = head
        var fastNode = head.next
        while fastNode?.next != nil {
            node = node.next!
            fastNode = fastNode?.next?.next//走两步
        }
        //左链表的头节点
        var rightHead = node.next
        //断开链表
        node.next = nil
        //后链表倒置
        if rightHead != nil && rightHead?.next != nil {
            var node = rightHead
            var nNode = rightHead?.next
            var pNode: ListNode? = nil
            
            while nNode != nil {
                let temp = nNode?.next
                nNode?.next = node
                node?.next = pNode
                pNode = node
                node = nNode
                nNode = temp
            }
            rightHead = node
        }
        var templ:ListNode? = head
        var tempr = rightHead
        //两链表进行穿插
        while templ != nil {
            let templl = templ?.next
            let temprr = tempr?.next
            templ?.next = tempr
            tempr?.next = templl
            templ = templl
            tempr = temprr
        }
    }
    
    /**
     给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
     你应当保留两个分区中每个节点的初始相对位置。
     输入: head = 1->4->3->2->5->2, x = 3
     输出: 1->2->2->4->3->5
     
     思路：
     找出大于等于x的节点的前节点
     对后面节点如果小于x进行插入操作
     */
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        guard head != nil && head?.next != nil else {
            return head
        }
        //哑结点
        let fNode = ListNode.init(-1)
        fNode.next = head
        var pNode: ListNode? = fNode
        while let node = pNode?.next, node.value < x {
            pNode = node
        }
        /* 虽然正确，但是LeetCode超时*/
//        var nNode = node?.next
//        var temp = node
//        while nNode != nil {
//            if nNode!.value < x {
//                temp?.next = nNode?.next
//                pNode?.next = nNode
//                nNode?.next = node
//                nNode = temp?.next
//                pNode = nNode
//            } else {
//                temp = nNode
//                nNode = nNode?.next
//            }
//        }
        var cur = pNode
        while cur?.next != nil {
            if cur!.next!.value < x {
                // 被删除的节点
                let deleted = cur?.next
                // 删除小于x的节点
                cur?.next = cur?.next?.next
                // 将删除节点插入
                deleted?.next = pNode?.next
                pNode?.next = deleted
                // 保证两个分区中每个节点的初始相对位置
                pNode = deleted
            } else {
                cur = cur?.next
            }
        }
        return fNode.next
    }
    
    /**
     给定两个用链表表示的整数，每个节点包含一个数位。
     这些数位是反向存放的，也就是个位排在链表首部。
     编写函数对这两个整数求和，并用链表形式返回结果。
     输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
     输出：2 -> 1 -> 9，即912
     
     思路：
     用新链表存储位数和以及进位
     最后处理尾结点
     */
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard l1 != nil && l2 != nil else {
            return (l1 != nil) ? l1:((l2 != nil) ? l2:nil)
        }
        var nodel = l1
        var noder = l2
        let head = ListNode.init(0)
        var temp: ListNode? = ListNode.init(-1)
        temp?.next = head
        while nodel != nil || noder != nil {
            let value = (nodel?.value ?? 0) + (noder?.value ?? 0) + temp!.next!.value
            temp!.next!.value = value%10
            temp!.next!.next = ListNode.init((value < 10) ? 0:1)
            temp = temp?.next
            nodel = nodel?.next
            noder = noder?.next
        }
        if temp!.next!.value == 0 {
            temp?.next = nil
        }
        return head
    }
    
    /**
     在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
     输入: 4->2->1->3
     输出: 1->2->3->4
     
     思路：
     利用归并排序 时间复杂度为O(nlogn)，由链表可以有一个移动指针则空间复杂度为O(1)
     利用递归思想分组，最后由分组合并
     */
    func sortList(_ head: ListNode?) -> ListNode? {
        guard head != nil && head?.next != nil else {
            return head
        }
        var slow = head
        var fast = head?.next
        while fast?.next != nil && fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        var headr = slow?.next
        var headl = head
        slow?.next = nil
        headl = sortList(headl)
        headr = sortList(headr)
        return merge(headl, headr)
    }
    
    fileprivate func merge(_ a: ListNode?, _ b: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        var pa = a
        var pb = b
        var p: ListNode? = dummy
        while pa != nil && pb != nil {
            if pa!.value < pb!.value {
                p?.next = pa
                pa = pa?.next
                p = p?.next
                p?.next = nil
            } else {
                p?.next = pb
                pb = pb?.next
                p = p?.next
                p?.next = nil
            }
        }
        if pa != nil {
            p?.next = pa
        }
        if pb != nil {
            p?.next = pb
        }
        return dummy.next
    }
        
}
//list.appendToTail(79)
//Solution().reorderList(list.head)

//var node = (Solution().partition(list.head, 4)) ?? ListNode(0)
//List.init(&node).getString()
//print(list.getString())

原文作者：Jonathan Lu

原文链接：https://jonathanlu98.github.io/2020/08/29/%E7%AE%97%E6%B3%95%E5%9F%BA%E7%A1%80%EF%BC%88%E5%9B%9B%EF%BC%89%E9%93%BE%E8%A1%A8%E7%BB%BC%E5%90%88/

发表日期：August 29th 2020, 9:54:01 pm

更新日期：October 5th 2021, 11:34:35 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

• Next Post
  算法基础（五）树综合
• Previous Post
  算法基础（三）排序和搜索

Powered by Hexotheme Archer

PV: :)

CATALOG

1. 1. 算法基础（四）链表综合

• Archive
• Tag
• Cate

Total : 15

2022

• 09/25 软件使用 - V2rayN For Windows 配置方式

2020

• 08/29 算法基础（五）树综合
• 08/29 算法基础（四）链表综合
• 08/29 算法基础（三）排序和搜索
• 08/29 算法基础（六） 题目综合
• 07/02 实习面试整理
• 06/10 算法基础（二）数据结构
• 05/03 算法基础（一）基本的数据结构（数组、集合、字典、字符串）
• 04/10 回顾C、C++、Java
• 03/06 OC-声明小记（一）
• 03/05 OC-枚举的学问

2019

• 11/12 项目分享 ：iSCUEC Demo 发布了
• 10/23 博客网站的迁移
• 08/13 iOS小记 ：第一次开发完成经历
• 01/19 如何使用Reveal

 iOS小记  分享  项目分享  实习准备  软件使用



缺失模块，请参考主题文档进行安装配置：https://github.com/fi3ework/hexo-theme-archer#%E5%AE%89%E8%A3%85%E4%B8%BB%E9%A2%98

