本文正在参加「金石方案 . 分割6万现金大奖」

前言：最近自己也开端体系的刷面试题了，算法是过不去的坎，希望自己能够坚持下去✊，同行的朋友们共勉。

题一：删去链表中的节点

有一个单链表的head，咱们想删去它其间的一个节点node。

给你一个需要删去的节点node。你将无法访问第一个节点head。

链表的一切值都是 唯一的，而且确保给定的节点node不是链表中的最后一个节点。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解说：指定链表中值为5的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

解题思路：直接替换

此题考察了链表的结构， 咱们在删去、增加元素时，只需要修改引证目标指针即可；

• 删去：去除引证联系，让当前节点被下一个节点代替
• 增加：被某个方位的节点引证

因为这里传入被删去的该节点，所以运用下一个节点来替换被删去节点就能够了。

func deleteNode(_ node: ListNode?, _ head: ListNode?) {
    node?.val = node?.next?.val ?? 0
    node?.next = node?.next?.next ?? nil
    let head = head
}

题二：删去链表的倒数第N个节点

给你一个链表，删去链表的倒数第n 个结点，而且回来链表的头结点。

示例 1：

输入： head = [1,2,3,4,5], n = 2
输出： [1,2,3,5]

解题思路：递归、双循环、快慢指针

这题同样在考察咱们对链表的理解。

链表是线性数据结构，咱们单从头节点中无法知道链表的长度。 经过遍历整个链表，咱们才能够知道链表的长度。而确定了链表的长度之后，再去找到要被删去的元素就简略了。

递归

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let pos = length(head, n)
    if pos == n {
        return head?.next
    }
    return head
}
func length(_ node: ListNode?, _ n: Int) -> Int {
    if node?.next == nil {
        return 1
    }
    /// 获取前面一个节点
    let pos = length(node?.next, n) + 1
    if pos == n+1 {
        print("\(pos)")
        node?.next = node?.next?.next
    }
    return pos
}

双循环

第一次：确定链表长度 第2次：定位到n的方位，完结替换

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
    let pos = length(head, n)
    if pos == n {
        return head?.next
    }
    return head
}
func length(_ node: ListNode?, _ n: Int) -> Int {
    if node?.next == nil {
        return 1
    }
    /// 获取前面一个节点
    let pos = length(node?.next, n) + 1
    if pos == n+1 {
        print("\(pos)")
        node?.next = node?.next?.next
    }
    return pos
}

快慢指针

fast、slow两个指针，fast先走n次，然后和slow一起移动。 slow和fast相距n， 当fast先走到链表底部，slow便是要删去的目标；

func removeNthFromEnd3(_ head: ListNode?, _ n: Int) -> ListNode? {
    var fast = head
    var slow = head
    var index = n
    /// jNode 移位 n
    while index > 0 {
        fast = fast?.next
        index-=1
        let j = fast
    }
    if fast?.next == nil { return head?.next }
    /// 开端遍历
    while fast?.next != nil {
        fast = fast?.next
        slow = slow?.next
    }
    slow?.next = slow?.next?.next
    return head
}

题三：回转链表

给你单链表的头节点head，请你回转链表，并回来回转后的链表。

示例 1：

输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]

解题思路：栈、递归、双指针

将单向链表翻转等于是改动链表方向；

栈操作

先进后出、后进先出。利用栈的特性，回转链表。

• 入栈：1 —> 2 —> 3
• 出栈：3 —> 2 —> 1

func reverseList(_ head: ListNode?) -> ListNode? {
    /// 悉数入栈
    var node = head
    var stack = Stack<ListNode>()
    while node != nil {
        if let node = node {
            stack.push(element: node)
        }
        node = node?.next
    }
    /// 第一个出栈的节点是新的表头
    node = stack.pop()
    /// 新的表头
    var newHead = node
    while !stack.isEmpty() {
        let tempNode = stack.pop()
        node?.next = tempNode
        node = tempNode
    }
    node?.next = nil
    return newHead
}

双指针

双指针：newHead、node
每次循环，缓存node指针的下一个节点，这里比较要害。 然后

func reverseList(_ head: ListNode?) -> ListNode? {
    var node = head
    var newhead: ListNode? = nil
    while node != nil {
        let temp = node?.next
        node?.next = newhead
        newhead = node
        node = temp
    }
    return newhead
}

题四：合并两个有序链表

将两个升序链表合并为一个新的升序链表并回来。新链表是经过拼接给定的两个链表的一切节点组成的。

示例 1：

输入： l1 = [1,2,4], l2 = [1,3,4]
输出： [1,1,2,3,4,4]

解题思路：双指针

合并两个升序的链表其实和数组的思想类似。只是完成上有点差异。可是都能够运用双指针去完成。 两个指针别离指向两个链表的头部节点，比较两个节点的值巨细，小的一方增加到链表中，而且把指针往后移。

func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
    var node1 = list1
    var node2 = list2
    var newHead = ListNode(0)
    var cur: ListNode? = newHead
    while node1 != nil && node2 != nil {
        let val1 = node1?.val ?? 0
        let val2 = node2?.val ?? 0
        if val1 <= val2 {
            cur?.next = node1
            node1 = node1?.next
        } else {
            cur?.next = node2
            node2 = node2?.next
        }
        cur = cur?.next
    }
    cur?.next = node1 == nil ? node2 : node1
    let head = newHead.next
    return head
}

题五：回文链表

给你一个单链表的头节点head，请你判别该链表是否为回文链表。假如是，回来true；不然，回来false。

示例 1：

输入： head = [1,2,2,1]
输出： true

解题思路：栈操作、递归、回转后半链表

要害点便是对比首尾的各个节点；怎么获取尾部的节点呢？答案是：栈操作、递归、回转后半链表。

递归也相当于栈操作

栈操作

先进后出、后进先出。

func isPalindrome(_ head: ListNode?) -> Bool {
    var node = head
    var stack = Stack<Int>()
    var length = 0
    while node != nil {
        if let node = node {
            stack.push(element: node.val)
        }
        node = node?.next
        length+=1
    }
    node = head
    length/=2
    while length > 0 {
        if node?.val != stack.pop() {
            return false
        }
        node = node?.next
        length-=1
    }
    return true
}

回转后半链表

先找到中间链表 运用快慢指针 fast、slow (原理：fast+2，slow+1，fast抵达终点，slow此刻应该在中间）

判别奇偶数，假如fast不为空，则说明链表长度为奇数，若fast为空，则说明为偶数，找到中点，回转后半部分链表

判别回转后的链表是否和前半部分链表相同，假如悉数相同则说明是回文链表，反之，则不是。

func isPalindrome(_ head: ListNode?) -> Bool {
    var fast = head
    var slow = head
    while fast != nil, fast?.next != nil {
        fast = fast?.next?.next
        slow = slow?.next
    }
    /// 奇数就选下一个
    if fast != nil {
        slow = slow?.next
    }
    var newNode = reverse(slow)
    var node = head
    while newNode != nil {
        if newNode?.val != node?.val {
            return false
        }
        newNode = newNode?.next
        node = node?.next
    }
    return true
}

题六：环形链表

给你一个链表的头节点 head ，判别链表中是否有环。

假如链表中有某个节点，能够经过接连跟踪 next 指针再次抵达，则链表中存在环。 为了表示给定链表中的环，评测体系内部运用整数 pos 来表示链表尾连接到链表中的方位（索引从 0 开端）。留意：pos 不作为参数进行传递。只是是为了标识链表的实际情况。

假如链表中存在环，则回来 true 。 不然，回来 false 。

示例 1：

输入： head = [3,2,0,-4], pos = 1
输出： true
解说： 链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入： head = [1], pos = -1
输出： false
解说： 链表中没有环。

解题思路：调集法、快慢指针

调集法

假如不考虑内存问题，咱们能够运用调集来缓存每次到访的节点。假如下一次命中缓存，则说明有环。

func hasCycle(_ head: ListNode?) -> Bool {
    var node = head?.next
    var set = Set<ListNode>()
    while node != nil {
        if set.contains(node!) {
            return true
        } else {
            set.insert(node!)
        }
        node = node?.next
    }
    return false
}

快慢指针

判别链表中有没有环，能够经过快慢指针来处理， slow走一步，fast走两步，假如有环，当走到n次时，slow和fast相遇。 假如没有环，fast会先走到尾部，变为nil。

func hasCycle(_ head: ListNode?) -> Bool {
    var slow = head?.next
    var fast = head?.next?.next
    while fast != nil {
        if slow === fast {
            return true
        }
        slow = slow?.next
        fast = fast?.next?.next
    }
    return false
}

小结

链表篇的初级算法看看你都学会了吗？链表的数据结构与数组的差异在于，数组在内存是接连的，而链表不需要接连。链表在刺进和删去上也比较灵敏，可是在查找时就比较费事，只能经过头节点一个个向后遍历查找。在许多链表的处理上，大多数都能够运用递归的方式。

链表：栈、递归、快慢指针、调集、双指针