怎么判别链表有环？

要判别一个链表是否有环，能够运用快慢指针的办法。

快慢指针是指两个指针，一个指针每次移动两步，称为快指针，另一个指针每次移动一步，称为慢指针。假如链表中存在环，那么快指针最终会在某个时刻追上慢指针，构成一个循环。

下面是运用快慢指针判别链表是否有环的算法：

界说两个指针，一个快指针 fast 和一个慢指针 slow，初始时都指向链表的头节点。
运用一个循环，每次循环中，快指针 fast 移动两步，慢指针 slow 移动一步。
在每次移动后，判别快指针 fast 和慢指针 slow 是否持平。假如持平，阐明链表中存在环，回来 true。
假如快指针 fast 移动到链表的结尾（即指向 null），则阐明链表没有环，回来 false。

下面是运用 Swift 言语完成的示例代码：

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

在上述代码中，运用两个指针 slow 和 fast，它们都指向链表的头节点 head。在每次循环中，slow 指针移动一步，fast 指针移动两步。假如链表中存在环，那么 fast 指针最终会追上 slow 指针，回来 true。假如 fast 指针移动到链表结尾（即指向 null），则阐明链表没有环，回来 false。

能够经过调用 hasCycle 函数来判别给定链表是否有环。

怎么判别两个单向链表是否相交，假如相交，求出交点

要判别两个单向链表是否相交，并找出它们的交点，能够运用以下办法：

遍历第一个链表，将每个节点的引证存储到一个调集（如哈希调集）中。
遍历第二个链表，对于每个节点，查看调集中是否存在相同的节点引证。假如存在，则阐明两个链表相交，交点即为当时节点。

下面是运用 Swift 言语完成的示例代码：

class ListNode: Hashable {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
    self.val = val
    self.next = nil
  }
  static func ==(lhs: ListNode, rhs: ListNode) -> Bool {
    return lhs === rhs
  }
  func hash(into hasher: inout Hasher) {
    hasher.combine(ObjectIdentifier(self).hashValue)
  }
}
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
    var set = Set<ListNode>()
    // 遍历第一个链表，将节点引证存储到调集中
    var nodeA = headA
    while nodeA != nil {
        set.insert(nodeA!)
        nodeA = nodeA?.next
    }
    // 遍历第二个链表，查看调集中是否存在相同的节点引证
    var nodeB = headB
    while nodeB != nil {
        if set.contains(nodeB!) {
            return nodeB
        }
        nodeB = nodeB?.next
    }
    // 假如没有相交点，回来空
    return nil
}

运用以上代码，能够经过调用 getIntersectionNode 函数来判别两个链表是否相交，并找出它们的交点。假如相交，函数将回来交点所在的节点；假如不相交，函数将回来 nil。

以下是一个测验用例的示例：

// 创立链表1
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
node1.next = node2
node2.next = node3
// 创立链表2
let node4 = ListNode(4)
let node5 = ListNode(5)
node4.next = node5
node5.next = node2 // 链表2与链表1相交于节点2
// 测验
if let intersectionNode = getIntersectionNode(node1, node4) {
    print("两个链表相交，交点的值为：(intersectionNode.val)") // 输出：两个链表相交，交点的值为：2
} else {
    print("两个链表不相交") // 不会履行到这儿
}

在这个测验用例中，咱们创立了两个链表，链表1的尾节点与链表2的节点2相交。调用 getIntersectionNode 函数来判别它们是否相交，并找出交点。预期输出为 “两个链表相交，交点的值为：2″。

在一个有环链表中，怎么找出链表的入环点？

要找出一个有环链表的入环点，能够运用快慢指针的办法。

以下是找出链表入环点的算法步骤：

运用快慢指针，一起从链表的头部出发，快指针每次行进两步，慢指针每次行进一步，直到它们相遇在某个节点上。
当快慢指针相遇时，将其间任一个指针移回链表的头部，另一个指针保持在相遇的节点上。
然后，两个指针一起以每次行进一步的速度移动，直到它们再次相遇。相遇的节点即为链表的入环点。

下面是运用 Swift 言语完成的示例代码：

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func detectCycle(_ head: ListNode?) -> ListNode? {
    var slow = head
    var fast = head
    var hasCycle = false
    // 判别是否存在环
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        if slow === fast {
            hasCycle = true
            break
        }
    }
    // 假如存在环，则找到入环点
    if hasCycle {
        slow = head
        while slow !== fast {
            slow = slow?.next
            fast = fast?.next
        }
        return slow
    }
    // 假如不存在环，则回来 nil
    return nil
}

运用以上代码，能够经过调用 detectCycle 函数来找出一个有环链表的入环点。假如链表存在环，则回来入环点的节点；假如链表不存在环，则回来 nil。

以下是一个测验用例的示例：

// 创立链表
let node1 = ListNode(1)
let node2 = ListNode(2)
let node3 = ListNode(3)
let node4 = ListNode(4)
let node5 = ListNode(5)
// 构造有环的链表，环的进口是节点2
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node2
// 测验
if let cycleStartNode = detectCycle(node1) {
    print("链表的入环点为：(cycleStartNode.val)") // 输出：链表的入环点为：2
} else {
    print("链表没有环") // 不会履行到这儿
}

在这个测验用例中，咱们创立了一个有环的链表，环的进口是节点2。调用 detectCycle 函数来找出链表的入环点，并输出其值为2。

单链表回转

要将一个单链表进行回转，能够运用迭代或递归两种办法。

迭代法

迭代法是经过遍历链表，逐一修正节点的指针指向来完成回转。

以下是运用迭代法回转单链表的示例代码：

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func reverseList(_ head: ListNode?) -> ListNode? {
    var prev: ListNode? = nil
    var curr = head
    while curr != nil {
        let nextTemp = curr?.next
        curr?.next = prev
        prev = curr
        curr = nextTemp
    }
    return prev
}

在上述代码中，咱们运用 prev 变量来保存已回转部分的头节点，初始时为 nil。然后，运用 curr 指针遍历链表，将每个节点的 next 指针指向其前一个节点 prev。最终，回来回转后的链表的头节点 prev。

递归法

递归法是经过递归地回转子链表来完成整个链表的回转。

以下是运用递归法回转单链表的示例代码：

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func reverseList(_ head: ListNode?) -> ListNode? {
    if head == nil || head?.next == nil {
        return head
    }
    let reversedHead = reverseList(head?.next)
    head?.next?.next = head
    head?.next = nil
    return reversedHead
}

在上述代码中，咱们首要判别链表是否为空或只有一个节点，假如是，则直接回来链表头节点。然后，经过递归调用 reverseList 函数来回转剩下的子链表，并将回来的回转后的子链表的头节点保存在 reversedHead 变量中。接下来，将当时头节点的下一个节点的 next 指针指向当时头节点，然后将当时头节点的 next 指针置为 nil，完成当时节点的回转。最终，回来 reversedHead，即整个链表回转后的头节点。

这是两种常用的办法来回转单链表。

兼并两个有序链表

要兼并两个有序链表，能够运用迭代或递归两种办法。

迭代法

迭代法是经过遍历两个有序链表的节点，逐一比较节点的值，并将较小值的节点链接到新链表中，最终得到兼并后的有序链表。

以下是运用迭代法兼并两个有序链表的示例代码：

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    let dummyHead = ListNode(0)
    var tail: ListNode? = dummyHead
    var p1 = l1
    var p2 = l2
    while let node1 = p1, let node2 = p2 {
        if node1.val < node2.val {
            tail?.next = node1
            p1 = node1.next
        } else {
            tail?.next = node2
            p2 = node2.next
        }
        tail = tail?.next
    }
    if let remainingNodes = p1 ?? p2 {
        tail?.next = remainingNodes
    }
    return dummyHead.next
}

在上述代码中，咱们首要创立一个虚拟头节点 dummyHead，用于保存兼并后的有序链表的头节点。然后，运用 tail 指针来追寻兼并后链表的尾部节点，初始时指向 dummyHead。一起，运用 p1 和 p2 分别指向两个有序链表的当时比较节点。

然后，经过比较 p1 和 p2 节点的值，将较小值的节点链接到新链表的尾部，并将相应指针向后移动。直到其间一个链表遍历完毕。

最终，假如还有剩下节点未处理完，将剩下节点链接到新链表的尾部。

最终，回来 dummyHead.next，即兼并后的有序链表的头节点。

递归法

递归法是经过递归地兼并两个有序链表的子问题，最终得到兼并后的有序链表。

以下是运用递归法兼并两个有序链表的示例代码：

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    guard let node1 = l1 else {
        return l2
    }
    guard let node2 = l2 else {
        return l1
    }
    if node1.val < node2.val {
        node1.next = mergeTwoLists(node1.next, node2)
        return node1
    } else {
        node2.next = mergeTwoLists(node1, node2.next)
        return node2
    }
}

在上述代码中，咱们首要处理特殊情况，即其间一个链表为空，直接回来另一个链表。

然后，比较两个链表的头节点的值，将较小值的节点作为兼并后的链表的头节点，并递归地兼并剩下部分。假如 l1 的头节点较小，则将 l1.next 和 l2 进行递归兼并；假如 l2 的头节点较小，则将 l1 和 l2.next 进行递归兼并。

最终，回来递归兼并后的结果。

这是两种常用的办法来兼并两个有序链表。

iOS必知必会链表常考算法题总结（附代码实现）

怎么判别链表有环？

怎么判别两个单向链表是否相交，假如相交，求出交点

在一个有环链表中，怎么找出链表的入环点？

单链表回转

迭代法

递归法

兼并两个有序链表

迭代法

递归法

作者信息

iOS必知必会链表常考算法题总结（附代码实现）

怎么判别链表有环？

怎么判别两个单向链表是否相交，假如相交，求出交点

在一个有环链表中，怎么找出链表的入环点？

单链表回转

迭代法

递归法

兼并两个有序链表

迭代法

递归法

相关文章

计算机网络 (5) 数据链路层-MAC地址、IP地址及ARP协议

浅看一下flutter_driver的源码

云计算运营—02 FusionSphere 6.5 服务器虚拟化运营

无埋点核心技术：iOS Hook在字节的实践经验

作者信息