概念
链表是由数据项组成的一个序列，其中每个数据项被称为节点。
链表有两种主要类型：
单链表
每一个节点只包含一个指向链表中下一个节点的指针（引用）。
单链表
双链表
每个节点包含两个指针（引用），一个指向前一个节点，一个指向后一个节点。
双链表
通常我们用head和tail指针来记录链表的头和尾。
链表头尾标记
Swift 实现
/// 链表节点类
public class ListNode<T> {
var value: T // 值
var next: ListNode<T>? = nil // 下一个节点
weak var previous: ListNode<T>? = nil
init(value: T) {
self.value = value
}
}
/// 链表类
public class LinkedList<T: Equatable> {
fileprivate var head: ListNode<T>? // 链表的头
private var tail: ListNode<T>? // 链表的尾
public var isEmpty: Bool {
return head == nil
}
public var first: ListNode<T>? {
return head
}
public var last: ListNode<T>? {
return tail
}
public func append(node: ListNode<T>) {
if let tailNode = tail {
tailNode.next = node
// node.previous = tailNode
}else {
head = node
}
tail = node
}
public func append(value: T) {
let newNode = ListNode<T>.init(value: value)
if let tailNode = tail {
tailNode.next = newNode
newNode.previous = tailNode
}else {
head = newNode
}
tail = newNode
}
/// node节点后插入值为val的节点
/// - Parameter node: 目标节点啊
/// - Parameter val: 插入的节点的值
func insert(node: ListNode<T>, val: T) {
let newNode = ListNode<T>.init(value: val)
newNode.next = node.next
node.next = newNode
}
public func nodeAt(index: Int) -> ListNode<T>? {
guard index >= 0 else {
return nil
}
var i = index
var node = head
while node != nil {
if i == 0 {
return node
}
node = node?.next
i -= 1
}
return nil
}
public func removeAll() {
self.head = nil
self.tail = nil
}
/// 删除一个节点（单向链表）
/// - Parameter node: 要删除的节点
/// 当需要删除一个节点p时，只需要将p的前一个节点的next赋为p->next,但是由于是单向的，只知道p，无法知道p前一个节点，所以需要转换思路。将p下一个的节点覆盖到p节点即可，这样就等效于将p删除了。
func deleteNode(node: ListNode<T>) {
if let next = node.next {
node.value = next.value
node.next = next.next
}else {
self.pop()
}
}
public func remove(node: ListNode<T>) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
return node.value
}
/// 去掉最后一个节点
public func pop() -> T? {
/// 存在最后一个节点
if let last = tail {
/// 存在最后一个节点的前一个节点
if let lp = last.previous {
lp.next = nil
tail = lp
}else {/// 不存在
head = nil
tail = nil
}
}
tail?.previous = nil
tail?.next = nil
return tail?.value
}
/// 找到循环链表的一个相同节点
///
/// - Returns: <#return value description#>
func fineMeetNode() -> ListNode<T>? {
guard let h = head else {
return nil
}
var fast: ListNode<T>? = h
var slow: ListNode<T>? = h
while (fast?.value != nil && fast?.next?.value != nil) { //两个变量赛跑，找出相遇的节点
fast = (fast?.next?.next)!
slow = slow?.next!
if (fast!.value == slow!.value) {
return slow
}
}
return nil
}
/// 找到循环链表的入口
///
/// - Returns: <#return value description#>
func findCycleEntrance() -> ListNode<T>? {
guard var meetNode = self.fineMeetNode() else {
return nil
}
while meetNode.value != self.head?.value {
meetNode = meetNode.next!
self.head = self.head?.next
}
return meetNode
}
}
使用
let dogbreeds = LinkedList<String>()
let d = ListNode.init(value: "Labrador")
let Bulldog = ListNode.init(value: "Bulldog")
let Beagle = ListNode.init(value: "Beagle")
let Husky = ListNode.init(value: "Husky")
dogbreeds.append(node: d)
dogbreeds.append(node: Bulldog)
dogbreeds.append(node: Beagle)
dogbreeds.append(node: Husky)
dogbreeds.append(node: Bulldog)
dogbreeds.nodeAt(index: 0)
dogbreeds.nodeAt(index: 0)?.value == dogbreeds.nodeAt(index: 4)?.value
dogbreeds.nodeAt(index: 2)
dogbreeds.nodeAt(index: 3)
let a = dogbreeds.fineMeetNode()?.value
let a1 = dogbreeds.findCycleEntrance()?.value
let b = dogbreeds.hsaCycle()
判断是否是循环链表：
- 1、 在节点ListNode中增加一个域，用于记录此节点是否已经被访问,如下ListNode中被注释掉代码。此方法简单，能找出环开始的节点，但是增加了链表的开销。如果链表非常大 则需要十分大的内存来保存此域。
func hsaCycle() -> Bool {
guard head != nil && head?.next != nil else {
return false
}
while head != nil {
if self.isVisit == false {
self.isVisit = true
}else {
return true
}
head = head?.next
}
return false
}
- 2、使用两个变量赛跑，一个变量走两步/次，一个变量走一步/次。 如果有环则两个变量必定会相逢，其中快的变量比慢的变量多走一圈。此算法 如果链表的环非常大 则需要较大的遍历时间。此算法同时也能找出环开始的地方
找出环开始的节点证明：设链表长度为N(每个节点访问一次) 链表头到达环开始节点长度为 s ，环的大小为S因为 快节点比慢节点多跑一圈 到达相遇节点, 设n为循环的次数。 所以有 2*n-n=S =》 n=S,即到达相遇节点的时候慢节点相当于刚好走了一个环的大小。所以慢节点走完链表N剩下的节点为N-S。而从头节点到环开始的距离s =N-S。所以从头结点开始和慢节点同时再走N-S步即能在环开始的地方相遇
/// 找到循环链表的一个相同节点
///
/// - Returns: <#return value description#>
func fineMeetNode() -> ListNode<T>? {
guard let h = head else {
return nil
}
var fast: ListNode<T>? = h
var slow: ListNode<T>? = h
while (fast?.value != nil && fast?.next?.value != nil) { //两个变量赛跑，找出相遇的节点
fast = (fast?.next?.next)!
slow = slow?.next!
if (fast!.value == slow!.value) {
return slow
}
}
return nil
}
/// 找到循环链表的入口
///
/// - Returns: <#return value description#>
func findCycleEntrance() -> ListNode<T>? {
guard var meetNode = self.fineMeetNode() else {
return nil
}
while meetNode.value != self.head?.value {
meetNode = meetNode.next!
self.head = self.head?.next
}
return meetNode
}
删除链表中倒数第n个节点
1->2->3->4->5, n=2。返回 1->2->3->5
注意：给定的n的大小小于链表的长度。
解题思路依然是快行指针，这次两个指针移动速度相同。但是一开始，第一个指针（指向头结点之前）就落后第二个指针n个节点。接着两者同时移动，当第二个移动到尾节点时，第一个节点的下一个节点就是我们要删除的节点。
代码如下：
/// 打印协议
extension LinkedList: CustomStringConvertible where T: CustomStringConvertible {
public var description: String {
/// 头节点
var head = self.head
var result: String = ""
/// 当前节点不等于nil
while head != nil {
result += head?.value.description ?? ""
head = head?.next
if head != nil {
result += "->"
}
}
return result
}
}
/// 移除倒数第n个节点
extension LinkedList where T == Int {
func removeNthFromEnd(head: ListNode<T>?, _ n: Int) -> ListNode<T>?{
guard let head = head else {
return nil
}
let dummy = ListNode<Int>.init(value: 0)
dummy.next = head
var prev: ListNode? = dummy
var post: ListNode? = dummy
/// 设置后一个节点的初始位置
for _ in 0..<n {
post = post?.next
}
/// 同时移动前后节点
while post != nil, post?.next != nil {
prev = prev?.next
post = post?.next
}
// 删除节点
prev?.next = prev?.next?.next
return dummy.next
}
}
let ll = LinkedList<Int>.init()
ll.append(value: 1)
ll.append(value: 2)
ll.append(value: 3)
ll.append(value: 4)
ll.append(value: 5)
ll.removeNthFromEnd(head: ll.head, 2)
let rrr = ll.description
// 结果： "1->2->3->5"
单链表翻转（递归实现）
/// 翻转链表(单向链表翻转)
/// - Parameter head: 返回翻转后的头节点
func reverse(head: ListNode<T>?) -> ListNode<T>? {
if head == nil || head?.next == nil {
return head
}
let newHeader = reverse(head: head?.next)
head?.next?.next = head
head?.next = nil
return newHeader
}
步骤解析
1、找到最后一个节点
a -> b -> c -> d -> e -> nil
newHeader = e -> nil
2、翻转最后一个节点(head是d)
head?.next.next = head
翻转之前：
newHeader = e -> nil
翻转之后：
self = a -> b -> c -> d -> e -> d -> e -> d -> e...
newHeader = e -> d -> e -> d -> e ....
2.1、断链：head?.next = nil
self = a -> b -> c -> d -> nil
newHeader = e -> d -> nil
3.翻转倒数第二个节点(head是c)
翻转之前：
self = a -> b -> c -> d -> nil
newHeader = e -> d -> nil
翻转之后：
self = a -> b -> c -> d -> c -> d -> c -> d -> c...
newHeader = e -> d -> c -> d -> c ....
3.1、断链：head?.next = nil
self = a -> b -> c -> nil
newHeader = e -> d -> c -> nil
4、最后一个节点翻转(head是a)
翻转之前：
self = a -> b -> nil
newHeader = e -> d -> c -> b -> nil
翻转之后：
self = a -> b -> a -> b -> a...
newHeader = e -> d -> c -> b -> a -> b -> a ....
3.1、断链：head?.next = nil
self = a -> nil
newHeader = e -> d -> c -> b -> a -> nil
至此：翻转已完成
