一周编程集训day2：链表

1 任务

链表：学习单链表知识，实践环形链表(142,要求至少两种方法！)及反转一个单链表(206)，不限制语言！

2 概念介绍

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

3 leetcode

1.142.环形链表

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。

python解答思路1：遍历单链表，同时将结点进行比较和加入哈希表，则环的入口是哈希表里的第一个重复的结点。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        hash_table = set()  # 初始化一个哈希表
        while head:  # 开始遍历单链表
            if head in hash_table:
                return head  # 返回哈希表中已存在的结点
            else:
                hash_table.add(head)  # 哈希表里没有的加入哈希表中
            head = head.next  # 结点后移
 
        return None  # 链表无环

leetcode提交结果：

python解答思路2：设置两个指针，比如慢指针一次移动一个结点，快指针一次移动两个结点。若有环，则两个指针会在环中某个位置相遇。经过计算会得知：头结点距环起点和相遇点距环起点距离一致。先找到相遇点，然后设置速度一致的两个指针，分别从起点和相遇点开始移动，直到两者相遇， 该点即为环起点。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        if head.next is None:
            return None
        first = second = head
        while second.next and second.next.next: # 注意判断条件
            first = first.next
            second = second.next.next
            if first == second: # 找到相遇点
                p = head # 从头节点开始遍历
                while first != p: # 需要进行数学上的计算
                    p = p.next
                    first = first.next
                return p
        return None

leetcode提交结果：

2.206. 反转链表

反转一个单链表。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

python解答思路：遍历链表，选择头插法

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, pre = head, None
 
        while cur:
            cur.next, pre, cur = pre, cur, cur.next  # python中的多赋值，属于一次赋值，是同时进行的，变量之间的相互赋值不受彼此影响。
        return pre

leetcode提交结果：