2、链表
今天主要学习链表，在Python中并没有链表的数据结构，需要自己写，看LeetCode其内部似乎已经定义好了，我只需要使用。目前目标是尝试自己解，解不出来时学习别人解法，理解后，自己实现一遍，对比总结。
- 对链表的常用技巧，添加哑节点，它的next节点指向链表的头节点。因为单链表的头节点没有上一个节点，在判断时经常需要额外判断，因此使用哑节点可以只考虑通用情况。
- while head:可以对链表进行遍历
2.删除链表中倒数第N个节点
自己吭哧半天还是没懂链表如何求长度，它的迭代和数组也不一样。需要了解链表内部是如何实现的，我看一些文章中定义的类，感觉自己还是没明白，所以还是先看题目，从解题中去摸索。
看官方解析说此题有三种方法：
1.暴力解法：计算链表的长度L【需要遍历一遍链表】；找到倒数第N个节点的前一个节点（L-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:
#定义一个计算链表长度的函数
def getLength(node: ListNode) -> ListNode:
length = 0
while node:
length += 1
node = node.next
return length
dummy = ListNode(0, head) #在链表头部创建哑变量
length = getLength(dummy)
cur = dummy #将链表浅层复制给cur，不复制最后只会返回删除后的变量
for i in range(1, length-n):
cur = cur.next #找到删除的前一个变量
cur.next = cur.next.next #将此变量的指针指向下下个变量
return dummy.next #返回dummy.next，因为dummy包括哑变量，所以要.next
2.栈：因为需要倒数，所以可使用栈。栈是先进后出，在遍历节点的时候将节点存入栈中，然后弹出第n个，弹出后的栈顶就是需要的节点，将此节点指向下下个节点。官方文档中的栈?，栈可以使用list实现，.append(n)可以添加元素，.pop()可以弹出元素。
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head) #增加哑变量
stack = [] #创建栈
cur = dummy
while cur:
stack.append(cur) #将链表的元素添加进栈
cur = cur.next
for i in range(n):
stack.pop() #将n个元素弹出，range是从0~n-1，刚好个数一致。
prev = stack[-1] #取栈顶元素
prev.next = prev.next.next #更改链接
return dummy.next
3.双指针：在解特定位置搜索的题可以采用双指针，fast指针和slow指针，fast指针先移动n，然后fast与slow一起移动，当fast指向最后一个指针时，slow指针指向的就是待删除的元素；因为需要删除的前一个元素，因此slow指针从哑变量开始更合适。
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head)
fast = head
slow = dummy #从0开始
for i in range(n):
fast = fast.next #先走n个
while fast:
fast = fast.next
slow = slow.next #fast遍历完成所对应的slow
slow.next = slow.next.next
return dummy.next
3.反转链表
看到反转链表第一印象是使用栈，但是其输出也要求是链表，那么在出栈的时候把其变成链表。链表重要的是它的一个指向。
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
stack = [None] #不写None会超时
while head:
stack.append(head)
head = head.next
head = stack.pop()
cur = head #得到头结点
while stack:
cur.next = stack.pop() #将之后pop的值给next
cur = cur.next #cur更新
return head
作者：qingyangwu14
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-zhan-shi-xian-by-qingyangwu14/
来源：力扣（LeetCode）
1.将指针反转，属于双指针迭代。直接思想是定义两个指针pre和cur，把cur.next = pre，然后cur指针向前移动，遍历完即可。但是如果直接设置，那么cur.next因为已经更改就无法转移到下一个，因此需要一个中间变量temp存储之前索引temp = cur.next，然后再执行cur.next = pre，然后进行移动，把当前的cur给pre：pre=cur，cur往下移动cur = temp。【这个逻辑自己想不清，需多练，看的播放最多的那个讲解视频】
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
#因为表头在末尾，所以返回pre
return pre
2.使用递归实现，递归要求有三个规则：
可以分解成子问题；子问题的求解方式与大问题一致；存在最小子问题。
因为此问题可以分解成头结点与子链表，并把指向进行反转。【从顶端来思考似乎能想明白。。。】
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
作者：tangweiqun
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/shi-pin-jiang-jie-die-dai-he-di-gui-hen-hswxy/
来源：力扣（LeetCode）
|