02：链表

算法面试其他篇

目录：

1.1 链表基础

　　1、链表遍历

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):
    def __init__(self, item, next=None):
        self.item = item
        self.next = next

def travel(head):
    cur = head
    while cur != None:
        print(cur.item)
        cur = cur.next

lst=Node(1,Node(2,Node(3,Node(4))))   # 1-->3-->3-->4
travel(lst)

　　2、链表反转

#! /usr/bin/env python
# -*- coding: utf-8 -*-
class Node(object):
    def __init__(self, item, next=None):
        self.item = item
        self.next = next

def list_reverse(head):
    if head == None:
        return None
    L, R, cur = None, None, head  # 左指针、有指针、游标
    while cur.next != None:
        L = R             # 左侧指针指向以前右侧指针位置
        R = cur           # 右侧指针前进一位指向当前游标位置
        cur = cur.next    # 游标每次向前进一位
        R.next = L        # 右侧指针指向左侧实现反转
    cur.next = R          # 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
    return cur

if __name__ == '__main__':
    '''
    原始链表：1 -> 2 -> 3 -> 4
    反转链表：4 -> 3 -> 2 -> 1
    '''
    lst = Node(1, Node(2, Node(3, Node(4))))  # 1-->3-->3-->4
    l2 = list_reverse(lst)  # 4-->3-->2-->1
    print(l2.item)  # 4
    print(l2.next.item)  # 3

　　3、判断链表是否成环

class Node(object):
    def __init__(self, item, next=None):
        self.item = item
        self.next = next

def exitLoop(LList):
    p1 = p2 = LList
    while p2 and p2.pnext: #当链表为空或者只有一个结点时，就不执行循环体里的程序，返回False
        p1 = p1.pnext
        p2 = p2.pnext.pnext
        if p1 == p2:
            return True
    return False


if __name__=="__main__":
    LList = Node(1)
    p1 = Node(2)
    p2 = Node(3)
    p3 = Node(4)
    p4 = Node(5)
    p5 = Node(6)
    LList.pnext = p1
    p1.pnext = p2
    p2.pnext = p3
    p3.pnext = p4
    p4.pnext = p5
    p5.pnext = p2
    print(exitLoop(LList))  # True

1.2 判断链表成环 & 找出环节点入口

　　1、判断链表成环

 　　　　　　1. 使用快慢两个指针，如果成环快慢指针必然有重合的机会

　　2、判断环入口

　　　　　　注：当 快慢指针第一次在环中相遇后，把慢指针指向 再次指回头部，当快慢指针再次相遇必然在 环入口

　　　　　　1. 我们假定链表头到环入口的距离是len，环入口到slow和fast交汇点的距离为x，环的长度为R。

　　　　　　2. slow和fast第一次交汇时:

　　　　　　　　　　设slow走的长度为：d = len + x，
　　　　　　　　　　而fast走的长度为：2d = len + nR + x，  (n >= 1)

　　　　　　3. 从而我们可以得知：2len + 2x = len + nR + x，即 len = nR - x，(n >= 1)。

　　　　　　4. len = nR - x 可得出当快慢指针再次相遇必然在环入口处

　　　　　　　　

 　　3、求下面链表环的入口位置

class Node():  # 定义一个Node类，构造两个属性，一个是item节点值，一个是节点的下一个指向
    def __init__(self, item=None, next=None):
        self.item = item
        self.next = next

'''1、判断是否成环'''
def is_loop(head):
    slowPtr = head  # 将头节点赋予slowPtr
    fastPtr = head  # 将头节点赋予fastPtr
    loopExist = False  # 默认环不存在，为False
    if head == None:  # 如果头节点就是空的，那肯定就不存在环结构
        return False
    while fastPtr.next != None and fastPtr.next.next != None:  # fastPtr的下一个节点和下下个节点都不为空
        slowPtr = slowPtr.next  # slowPtr每次移动一个节点
        fastPtr = fastPtr.next.next  # fastPtr每次移动两个节点
        if slowPtr == fastPtr:  # 当fastPtr和slowPtr的节点相同时，也就是两个指针相遇了
            return fastPtr

'''2、判断环节点起始位置'''
def beginofloop(head):
    loop_tag = is_loop(head)  # 如果不为None代表没有成环
    if loop_tag:
        slowPtr = head              # 将慢指针再次指向头结点
        fastPtr = loop_tag          # 快指针从第一次相遇位置开始
        while slowPtr != fastPtr:   # 快慢指针再次相遇位置就是入口位置
            fastPtr = fastPtr.next
            slowPtr = slowPtr.next
        return slowPtr   # 返回换节点开始位置
    else:
        return False    # 没有成环

if __name__ == "__main__":
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node5.next = node2
    print(beginofloop(node1).item)   # 打印成环的其实位置

　　　　　　

111