第 1 关 | 原来链表这么有用：3.黄金挑战——链表中环的问题与双向链表

本关我们只研究两道题，一个是链表中环的问题，一个是双向链表问题。
具体来说是两道题。如何确定链表中环的问题，这个问题如果用Hash或者集合非常简单，但是在面试的时候如果这么做就没什么思维含量了，所以我们需要另外想办法。
如何寻找入口问题，代码非常简单，难点是难以想明白，所以嘛，加油，好好想想！
双向链表在工程里有很多应用，在操作系统、JVM等基础框架也有大量应用，因此也非常值得我们学习。

1. 链表中环的问题

本题同样是链表的经典问题。给定一个链表，判断链表中是否有环，这就是LeetCode141。进一步，假如有环，那环的位置在哪里？这就是LeetCode 142题。
这个问题前一问相对容易一些，后面一问比较难想到。但是，假如面试遇到第一问了，面试官很可能会问第二个，因为谁都知道有这个一个进阶问题。就像你和女孩子表白成功后，你会忍不住进阶一下——“亲一个呗”，一样的道理，所以我们都要会。

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

判断是否有环，最简单的方法就是 Hash ，遍历的时候将元素放到 map 中去，如果有环一定会发生碰撞。发生碰撞的位置也就是入口的位置，因此这个题so easy。如果在工程中，我们这么做就OK了，代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set set = new HashSet();

        while(pos != null){
            if(set.contains(pos)){
                return pos;
            }else{
                set.add(pos);
            }
             pos = pos.next;
        }
        return pos;
    }
}

class Solution:
    def hasCycle(self, head) :
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

由于C语言本身没有栈和集合结构，这里不提供参考代码。
如果只用 O(1)的空间该怎么做呢？我们逐步来分析。首先我们先来思考，为什么快慢指针一定会相遇，之后再来看如何解决问题。

1.1. 为什么快慢指针一定会相遇

上面那种做法虽然可以做出来，但是你会发现，这种做法的时间复杂度是 O（n），可能比较高，这个时候就可以考虑另外的一种方法，即双指针，一个快指针（一次走两步），一个慢指针（一次走一步）。如果快的能到达表尾就不会有环，否则如果存在环，则慢指针一定会在某个位置与快指针相遇。这就像在操场长跑，一个人快一个人慢，只要时间够，快的一定能在某个时候再次追上慢的人(也就是所谓的套圈)。
这里很多人可能会有疑问，因为两者每次走的距离不一样，会不会快的人在追上慢的时候跳过去了导致两者不会相遇呢？
不会！如下图所示，当fast快要追上slow的时候，fast一定距离slow还有一个空格，或者两个空格，不会有其他情况。

• 假如有一个空格，如上图情况1所示，fast和slow下一步都到了3号位置，因此就相遇了。
• 假如有两个空格，如上图情况2所示，fast下一步到达3，而slow下一步到达4，这就变成了情况1了，因此只要有环，一定会相遇。

使用双指针思想寻找是否存在环的方法：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null &&fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head: ListNode) -> bool:
    if head is None or head.next is None:
        return False

    fast = head
    slow = head

    while fast is not None and fast.next is not None:
        fast = fast.next.next
        slow = slow.next

        if fast == slow:
            return True

    return False

bool hasCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return false;
    }

    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow) {
            return true;
        }
    }

    return false;
}

1.2. 确定入口的方法

这里的问题是如果知道了一定有入口，那么如何确定入口的位置呢？方法非常简单，但是要理解清楚有些难度。
先说结论先按照快慢方式寻找到相遇的位置（假如为下图中Z），然后将两指针分别放在链表头（X）和相遇位置（Z），并改为相同速度推进，则两指针在环开始位置相遇（Y）。
结论很简单，但这是为什么呢？
①先看假如一圈就遇到的情况

为了便于理解，我们首先假定快指针在第二次进入环的时候就相遇了：
此时的过程是：
1.找环中相汇点。分别用fast、slow表示快慢指针，slow每次走一步，fast就走两步，直到在环中的某个位置相会，假如是图中的Z。
2.第一次相遇：
那么我们可以知道fast指针走了a+b+c+b步，
slow指针走了a+b步
那么：
2*(a+b) = a+b+c+b
所以a = c
因此此时让slow从Z继续向前走，fast回到起点，两个同时开始走（两个每次都走一步），一次走一步那么它们最终会相遇在y点，正是环的起始点。
② 如果多圈之后才相遇
如果是走了多圈之后才遇到会怎么样呢？ 设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为：
Fast: a+n(b+c)+b=a+(n+1)b+nc
根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有：
a+(n+1)b+nc=2(a+b)
由于b+c就是环的长度，假如为LEN，则：
a=c+(n-1)LEN
这说明什么呢？说明相遇的时候快指针在环了已经转了(n-1)LEN圈，如果n-1就退化成了我们上面说的一圈的场景。假如n是2 ，3，4，...呢，这只是说明当一个指针p1重新开始从head走的时候，另一个指针p2从Z点开始，两者恰好在入口处相遇，只不过p2要先在环中转n-1圈。
当然上面的p1和p2要以相同速度，我们发现slow和fast指针在找到位置Z之后就没有作用了，因此完全可以用slow和fast来代表p1和p2。因此代码如下：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast

struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast != NULL) {
        slow = slow->next;

        if (fast->next != NULL) {
            fast = fast->next->next;
        } else {
            return NULL;
        }

        if (fast == slow) {
            struct ListNode* ptr = head;

            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }

            return ptr;
        }
    }

    return NULL;
}

1.3. 【拓展】第二种确认入口的位置

这种方法与上面的相比要好理解一点，但是代码实现比较复杂一些。
如果还要确定环的入口，例如上面的图，指针从-4指向了2，要输出node(2)，该怎么做呢？
本节和下一节各介绍一种方法，本节的方法好想，但是代码不好写。下一节的问题代码好写但是不好想。
三次双指针的思想是：如果我们确定了环的大小和末尾结点，那该问题就退化成了找倒数第K个结点。我们来分析一下：
问题1：怎么判断环的大小呢？首先我们应该先判断是否存在环，此时可以使用上面说的快慢指针，我们假设fast和slow最后在P点。那接下来只要将一个指针例如slow固定在P位置，另一个fast从P开始遍历，显然，当fast=slow的时候自然就得到环的长度了。
问题2：那如何确定末尾结点呢？在上图中，我们注意到如果入口是node(2)，那我们遍历的时候如果指针p.next=node(2)就说明p就是链表的终点。
到此，这就是三次双指针方法：
第一次使用快慢指针判断是否存在环， fast一次走两步，slow一次走一步来遍历，如果最终相遇说明链表是否存在环。
第二次使用双指针判断环的大小，一个固定在相遇位置不动，另一个从相遇位置开始遍历，当两者再次相等的时候就找到了环的大小，假如为K。
第三次使用找倒数第K个结点的方法来找入口，根据上面2.4.2介绍的方法找倒数第K个元素的方法来找环的入口位置。
理解到这里，你能够将代码写出来？

2. 双向链表（C 版本）

2.1. 基本概念

双向链表顾名思义就是既可以向前，也可以向后。有两个指针的好处自然是移动元素更方便。该结构我们在工程里有大量的应用，本章我们看一下相关的基本问题。

双向链表的结点：

    struct DoubleNode *next;    // 指向下一个结点
    struct DoubleNode *prev;
} DoubleNode;

// 创建新结点
DoubleNode* newNode(int data) {
    DoubleNode *newNode = (DoubleNode*)malloc(sizeof(DoubleNode));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 打印结点的数据域
void displayNode(DoubleNode *node) {
    printf("%d ", node->data);
}

我们再定义一下双向链表遍历的完整方法：

void traverse(DoubleNode *head) {
    DoubleNode *p = head;  // 定义指针p，指向头节点
    while (p != NULL) {
        printf("%d ", p->data);  // 输出当前节点的数据域值
        p = p->next;  // 移动指针p到下一个节点
    }
}

2.2. 插入元素

操作双向链表的方法稍微复杂一些，而且头部、尾部和中间位置的操作有较大的区别，我们分别看。
我们先插入，在头部和尾部插入的方式稍微简单，直接上代码：
我们先定义两个全局变量，分别表示链表头和尾：

DoubleNode *first, *last;

//头部插入
void insertFirst(int data) {
    DoubleNode* newDoubleNode = (DoubleNode*)malloc(sizeof(DoubleNode));
    newDoubleNode->data = data;
    if (first == NULL) {
        last = newDoubleNode;
    } else {
        newDoubleNode->prev = first;
    }
    newDoubleNode->next = first;
    first = newDoubleNode;
}

//尾部插入
void insertLast(int data) {
    DoubleNode* newDoubleNode = (DoubleNode*)malloc(sizeof(DoubleNode));
    newDoubleNode->data = data;
    if (first == NULL) {
        first = newDoubleNode;
    } else {
        newDoubleNode->prev = last;
        last->next = newDoubleNode;
    }
    last = newDoubleNode;
}

对于上面的代码，很多人可能不太理解，我们现在以insertFirst()为例，从双向链表为空，到插入 20、40、60看一下队列的情况：
首先： first和last都指向null。
因为first和last都不是结点，我们下图用虚线表示
第一步：插入元素40：
先看执行如下代码的时候结构：

然后执行了first = newDoubleNode; 之后的结构是：

这样就插入了第一个元素。
（3）继续插入40的过程：
我们先执行两行代码，此时结构：

然后执行first = newDoubleNode; 之后：

这样就可以看到首元素从40开始，后面是20。
（4）继续插入60：
首先执行前两行代码：

然后再执行first = newDoubleNode;此时结构如下：

测试代码：

void insertDemo(){

    insertFirst(20);
    insertFirst(30);
    insertFirst(40);

    insertLast(50);
    insertLast(30);
    insertLast(10);

   traverse(first);
}

我们再看一下在中间位置插入的情况：

找到插入的位置之后，我们需要给newNode接四根线，假如上图中data2是当前结点，你能分析出连线的顺序吗？（提示：不止一种情况）

void insertAfter(int key, int data)
{
    DoubleNode *newDoubleNode = (DoubleNode *)malloc(sizeof(DoubleNode));
    newDoubleNode->data = data;
    DoubleNode *current = first;
    //current为null有两种情况 一种是链表为空，一种是找不到key值
    if (current == NULL)
    {
        if (first == NULL) //1、链表为空
        {
            first = newDoubleNode; //则插入第一个结点（其实可以调用其它的Insert方法）
            last = newDoubleNode; //first和last均指向该结点（第一个结点）
        }
        else //2、找不到key值，则在链表尾部插入一个新的结点
        {
            last->next = newDoubleNode;
            newDoubleNode->prev = last;
            last = newDoubleNode;
        }
    }
    else{
        if (current == last) //第三种情况，找到了key值，分两种情况
        { //1、key值与最后结点的data相等，由于newNode将是最后一个结点，则将last指向newNode
            newDoubleNode->next = current->next;
            last = newDoubleNode;
        }
        else //2、两结点中间插入
        {
            newDoubleNode->next = current->next;
            current->next->prev = newDoubleNode;
        }
        current->next = newDoubleNode;
        newDoubleNode->prev = current;
    }
}

测试代码：

void insertDemo()
{

    // insertFirst(20);
    // insertFirst(30);
    // insertFirst(40);

    insertLast(20);
    insertLast(60);
    insertLast(70);

    insertAfter(20, 70);
    insertAfter(20, 90);

    traverse(first);
}

2.3. 删除元素

双向链表的不足就是增删改的时候，需要修改的指针多了，操作更麻烦了。由于双向链表在算法中不是很重要，我们先看一下删除的大致过程。首尾元素的删除还比较简单，直接上代码：

//删除首元素
DoubleNode *deleteFirst()
{
    if (first == NULL)
    {
        return NULL;
    }

    DoubleNode *temp = first;
    if (first->next == NULL)
    {
        last = NULL;
    }else{
        first->next->prev = NULL;
    }

    first = first->next;

    return temp;
}

// 删除尾部元素
DoubleNode *deleteLast()
{
    if (first == NULL)
    {
        return NULL;
    }

    DoubleNode *temp = last;
    // 如果链表只有一个结点，则删除以后为空表,last指向null
    if (first->next == NULL)
    {
        first = NULL;
    }
    else

测试代码：

void deleteDemo()
{
    insertLast(20);
    insertLast(60);
    insertLast(70);
    deleteFirst(); // 删除20
    deleteLast(); //删除70
    traverse(first);
}

我们再看删除中间元素的情况，要标记出几个关键结点的位置，也就是图中的cur，cur->next和cur->prev结点。由于在双向链表中可以走回头路，所以我们使用cur，cur->next和cur->prev任意一个位置都能实现删除。假如我们就删除cur，图示是这样的：

我们只需要调整两个指针，一个是cur->next的prev指向cur->prev，第二个是cur->prev的next指向cur.next。此时cur结点没有结点访问了，然后就可以将cur删掉了，所以这样就完成了删除cur的操作。想一下，这里调整两条线的代码是否可以换顺序？

DoubleNode* deleteKey(int key) {
    DoubleNode* current = first;
    //遍历链表寻找该值所在的结点
    while (current != NULL && current->data != key) {
        current = current->next;
    }
    //若当前结点指向null则返回null
    if (current == NULL) {
        return NULL;
    } else {
        //如果current是第一个结点
        if (current == first) {
            //将first指向它，将该结点的previous指向null，其余不变
            first = current->next;
            if (current->next != NULL) {
                current->next->prev = NULL;
            }
        } else if (current == last) {
            //如果current是最后一个结点
            last = current->prev;
            current->prev->next = NULL;
        } else {
            //当前结点的上一个结点的next域应指向当前的下一个结点
            current->prev->next = current->next;
            //当前结点的下一个结点的previous域应指向当前结点的上一个结点
            current->next->prev = current->prev;
        }
    }
    return current; //返回
}

测试代码：

void deleteDemo()
{
    insertLast(20);
    insertLast(60);
    insertLast(70);
    deleteFirst(); // 删除20
    deleteLast(); //删除70
    traverse(first);
}

3. 双向链表设计（Java / Python 版本）

3.1. 基本概念

双向链表顾名思义就是既可以向前，也可以向后。有两个指针的好处自然是移动元素更方便。该结构我们在工程里有大量的应用，本章我们看一下相关的基本问题。

双向链表的结点：

class DoubleNode {
    public int data;    //数据域
    public DoubleNode next;    //指向下一个结点
    public DoubleNode prev;
    public DoubleNode(int data) {
        this.data = data;
    }
    //打印结点的数据域
    public void displayNode() {
        System.out.print("{" + data + "} ");
    }
}

class Node():
    def __init__(self, elem):
        # 双向链表结点
        self.pre = None
        self.elem = elem
        self.next = None

我们再定义一下双向链表的结构和遍历的方法：

public class DoublyLinkList {
    private DoubleNode first;
    private DoubleNode last;
    public DoublyLinkList() {
        first = null;
        last = first;
    }
    //从头部开始打印
    public void displayForward() {
        System.out.print("List(first--->last): ");
        DoubleNode current = first;
        while (current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }

    //从尾部开始演绎
    public void displayBackward() {
        System.out.print("List(last--->first): ");
        DoubleNode current = last;
        while (current != null) {
            current.displayNode();
            current = current.prev;
        }
        System.out.println();
    }
}

def length(self):
    # 链表长度
    if self.is_empty():
        return 0
    count = 0
    cur = self.__head
    while cur.next is not None:
        count += 1
        cur = cur.next
    return count

def travel(self):
    # 遍历整个链表
    if self.is_empty():
        return
    cur = self.__head
    while cur.next is not None:
        print(cur.elem)
        cur = cur.next
    print(cur.elem)

3.2. 插入元素

操作双向链表的方法稍微复杂一些，而且头部、尾部和中间位置的操作有较大的区别，我们分别看。
我们先插入，在头部和尾部插入的方式稍微简单，直接上代码：

//头部插入
public void insertFirst(int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    if (first == null) {
        last = newDoubleNode;
    } else {//如果不是第一个结点的情况
        //将还没插入新结点之前链表的第一个结点的previous指向newNode
        first.prev = newDoubleNode;    
    }
    newDoubleNode.next = first;
    //将新结点赋给first（链接）成为第一个结点
    first = newDoubleNode;            
}
//尾部插入
public void insertLast(int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    if (first == null) {
        first = newDoubleNode;        
    } else {
        newDoubleNode.prev = last;
        last.next = newDoubleNode;    
    }
    //由于插入了一个新的结点，又因为是尾部插入，所以将last指向newNode
    last = newDoubleNode;                
}

对于上面的代码，很多人可能不太理解，我们现在以insertFirst()为例，从双向链表为空，到插入 20、40、60看一下队列的情况：
首先： first和last都指向null。
因为first和last都不是结点，我们下图用虚线表示
第一步：插入元素40：
先看执行如下代码的时候结构：

然后执行了first = newDoubleNode; 之后的结构是：

这样就插入了第一个元素。
（3）继续插入40的过程：
我们先执行两行代码，此时结构：

然后执行first = newDoubleNode; 之后：

这样就可以看到首元素从40开始，后面是20。
（4）继续插入60：
首先执行前两行代码：

然后再执行first = newDoubleNode;此时结构如下：

这样，我们链表的首部就是first指向的结点60，然后向前到 40 和20，最后一个元素last就在node(20)处。

def add(self, item):
    # 链表头部添加元素
    node = Node(item)
    if self.is_empty():  # 原本是空链表的就让头指针直接指向这个新添加的元素结点
        self.__head = node
    else:  # 链表不为空时
        node.next = self.__head  # 新结点的next指针指向头指针所指的结点
        self.__head.pre = node.next  # 再将头指针结点的pre指针指向新结点的next
        self.__head = node  # 最后修改头指针指向新结点

def append(self, item):
    # 链表尾部添加元素
    # 创建新结点
    node = Node(item)
    # 是空链表就把头节点指向这个节点
    if self.is_empty():
        self.__head = node
    else:
        cur = self.__head
        while cur.next is not None:  # 循环找到尾部结点的指向，当退出循环时指针已指向最后一个结点
            cur = cur.next
        cur.next = node  # 将尾部结点的next指向新结点
        node.pre = cur.next  # 新结点的pre指向尾结点的next

我们再看一下在中间位置插入的情况：

找到插入的位置之后，我们需要给newNode接四根线，假如上图中data2是当前结点，你能分析出连线的顺序吗？（提示：不止一种情况）

public void insertAfter(int key, int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    DoubleNode current = first;
    while ((current != null) && (current.data != key)) {
        current = current.next;
    }
    //若当前结点current为空
    if (current == null) {                    
        if (first == null) {                    
            first = newDoubleNode;                
            last = newDoubleNode;                    
        } else {
            //2、找不到key值，则在链表尾部插入一个新的结点
            last.next = newDoubleNode;       
            newDoubleNode.prev = last;  
            last = newDoubleNode;
        }
    } else {//第3种情况，找到了key值，分两种情况
        if (current == last) {  
            //1、key值与最后结点的data相等
            newDoubleNode.next = null;            
            last = newDoubleNode;                    
        } else {
            //2、两结点中间插入   
            newDoubleNode.next = current.next;                                                                                                                                
            current.next.prev = newDoubleNode;    
        }                                        
        current.next = newDoubleNode;                    
        newDoubleNode.prev = current;                
    }
}

def insert(self, pos, item):
    # 位置pos在第一个元素之前，则在头部插入
    if pos  self.length():
        self.append(item)
    else:
        # 指定位置添加元素
        # 创建新结点
        node = Node(item)
        count = 0
        cur = self.__head  # 当时指针
        while count < (pos-1):  # 循环找到指向pos位置结点的指针
            count += 1
            cur = cur.next
        # 当上面退出循环时，说明cur已经指向了pos的位置
        # 所以接下来修改四个指针的指向来实现插入元素
        cur.next.pre = node.next  # 1.将cur的下一结点的pre指向新结点next
        node.next = cur.next  # 2.将新结点的next指向cur的下一结点
        cur.next = node  # 3.将cur的next指向新结点
        node.pre = cur.next  # 4.将新结点的pre指向cur的next

3.3. 删除元素

双向链表的不足就是增删改的时候，需要修改的指针多了，操作更麻烦了。由于双向链表在算法中不是很重要，我们先看一下删除的大致过程。首尾元素的删除还比较简单，直接上代码：

//删除首元素
public DoubleNode deleteFirst() {
    DoubleNode temp = first;
    //若链表只有一个结点，删除后链表为空，将last指向null
    if (first.next == null) {            
        last = null;
    } else {
        //若链表有两个及以上的结点 ，因为是头部删除，则first.next将变成第一个结点，其previous将变成null
        first.next.prev = null;        
    }
    //将first.next赋给first
    first = first.next;
    //返回删除的结点
    return temp;                    
}

//从尾部删除结点
public DoubleNode deleteLast() {
    DoubleNode temp = last;
    //如果链表只有一个结点，则删除以后为空表,last指向null
    if (first.next == null) {        
        first = null;
    } else {
        //将上一个结点的next域指向null
        last.prev.next = null;    
    }
    //上一个结点称为最后一个结点，last指向它
    last = last.prev;   
    //返回删除的结点
    return temp;                   
}

我们再看删除中间元素的情况，要标记出几个关键结点的位置，也就是图中的cur，cur.next和cur.prev结点。由于在双向链表中可以走回头路，所以我们使用cur，cur.next和cur.prev任意一个位置都能实现删除。假如我们就删除cur，图示是这样的：

我们只需要调整两个指针，一个是cur.next的prev指向cur.prev，第二个是cur.prev的next指向cur.next。此时cur结点没有结点访问了，根据垃圾回收算法，此时cur就变得不可达，最终被回收掉，所以这样就完成了删除cur的操作。想一下，这里调整两条线的代码是否可以换顺序？

public DoubleNode deleteKey(int key) {
    DoubleNode current = first;
    //遍历链表寻找该值所在的结点
    while (current != null && current.data != key) {        
        current = current.next;
    }
    //若当前结点指向null则返回null，
    if (current == null) {                        
        return null;                       
    } else {
        //如果current是第一个结点
        if (current == first) {
            //则将first指向它，将该结点的previous指向null,其余不变
            first = current.next;            
            current.next.prev = null;
        } else if (current == last) { 
            //如果current是最后一个结点
            last = current.prev;        
            current.prev.next = null;   
        } else {
            //当前结点的上一个结点的next域应指向当前的下一个结点
            current.prev.next = current.next;
            //当前结点的下一个结点的previous域应指向当前结点的上一个结点
            current.next.prev = current.prev;    
        }
    }
    return current;        //返回
}

def remove(self, item):
    # 删除节点
    cur = self.__head  # cur当前指针
    forword = None  # 前一个指针
    # 遍历链表当时指针
    while cur is not None:
        # 如果找到了要删除的元素
        if cur.elem == item:
            # 要删除的元素刚好是头部元素，就把头指针指向当前的下一个结点
            if cur == self.__head:
                self.__head = cur.next
            else:
                forword.next = cur.next  # 如果不是头元素指针就继续向后走
            return
        else:  # 未找到要删除的元素，指针向后走，继续遍历
            forword = cur
            cur = cur.next

4. 通关文牒

本关略有些难度，如何寻找环的入口，你想清楚了，自己能写出来就算通关啦