LeetCode——链表篇
一、移除链表元素
题解
该题其实就只需要遍历一下链表，需要注意的是，做这种题目的时候，最好新建一个头结点，否则在执行删除操作的时候难以进行。删除操作是链表中最基本的操作，需要熟练掌握。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(None)#新建一个虚拟头结点
dummy.next = head
cur = dummy
while cur.next:
if cur.next.val==val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
二、反转链表
题解
对于刚学过数据结构的同学来说，如果让你翻转链表，第一想法可能就是头插法，这种方法也比较好实现，在这里给出双指针和递归两种解法。
代码
双指针
#双指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while(cur!=None):
temp = cur.next # 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur.next = pre #反转
#更新pre、cur指针
pre = cur
cur = temp
return pre
递归
其实这个递归和双指针解法大致相同，理解了双指针，递归也很好实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
def reverse(pre,cur):
if not cur:
return pre
tmp = cur.next
cur.next = pre
return reverse(cur,tmp)
return reverse(None,head)
递归二
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
三、两两交换链表中的节点
题解
新建一个虚拟头结点dummy，三个节点为一组，要画图把逻辑搞清楚，一定要记得在断链前，用一个指针指向下一个节点。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None:
return None
if head.next is None:
return head
dummy = ListNode(None)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
tmp1 = cur.next #记录临时节点
tmp2 = cur.next.next.next #记录临时节点
cur.next = cur.next.next #步骤一
cur.next.next = tmp1 #步骤二
cur.next.next.next = tmp2 #步骤三
cur = cur.next.next
return dummy.next
四、删除链表的倒数第 N 个结点
题解
使用双指针的方式解决这个问题，设置两个指针，slow，fast，先让fast走N步，然后两个指针再一起移动，当fast移动到最后一个节点时，slow指针就在倒数第N个节点。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(None)
dummy.next = head
slow,fast = dummy,dummy
while n!=0:
fast = fast.next
n -= 1
while fast.next != None:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
其实这道题还有一个暴力解答，倒数第k个节点其实就是正数第len(head)-k+1个节点，需要注意的是len函数并不自带，需要自己定义
五、相交链表
题解
使用双指针，为了确保两个链表同时到达最后一个节点，先计算出两个链表的长度之差dist，long指针指向长的链表，short指向短的链表，并先让long走dist步，然后再同步移动。当long==short的时候，就说明遇到了公共节点。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
#当有一个为空时返回Null
if headA is None or headB is None:
return None
#通过while循环获取每一个链表的长度
curA = headA
curB = headB
lengthA,lengthB = 0,0
while curA != None:
curA = curA.next
lengthA += 1
while curB != None:
curB = curB.next
lengthB += 1
#将long指针指向长度长的那个
if lengthA > lengthB:
dist = lengthA-lengthB
long = headA
short= headB
else:
dist = lengthB-lengthA
long = headB
short = headA
#让长的先走dist步
while dist != 0:
long = long.next
dist -= 1
#如果long和short相遇，则说明遇到公共节点
while long != None and short != None:
if long == short:
return long
long = long.next
short = short.next
return None
六、环形链表
题解
可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。
可以自己画出整个过程，可以更好的理解逻辑
代码
'''
快慢指针，只要有环，两个指针必回相遇
'''
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head is None:
return False
slow,fast = head,head
while fast!=None:
fast = fast.next
if fast != None:
fast = fast.next
if fast==slow:
return True
slow = slow.next
return False
七、环形链表 ||
题解
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
以上题解来自代码随想录 Carla大佬的题解，感觉很清楚就搬过来了
代码
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if head is None:
return None
slow,fast = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow==fast: #相遇说明遇到了环
index1 = head
index2 = fast
while index1!=index2:
index1 = index1.next
index2 = index2.next
return index2
return None
