19. 删除链表的倒数第N个结点
题目描述
删除链表的倒数第n个结点，并且返回链表的头节点
思路
1. 先确定链表结点数，得到length
2. 再遍历到第length-n个结点上，改变其指针域上面的值为指向下下的结点，或者说使得指针域的值和下一个结点内指针域的值相等，实现删除第n个结点的功能
3. 暂且不考虑特殊情况，取cur=head，遍历length-n-1次到达目的地，此时cur指向第length-n个结点，执行上一步指针域重新赋值的操作
4. 考虑特殊情况，单列出来，当length-n=0，那么length-1小于小于0，会出现问题。
5. 单独解决这个问题，创建一个虚拟头指针，等于说是实现了cur向右移动-1步的操作，然后再执行指针域重新赋值的操作，返回dummy.next。
（貌似leetcode中的head就是第一个结点地址的意思，head.value就是第一个值，head.next就是下一个节点的地址值）
代码如下
# 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: Optional[ListNode], n: int) -> Optional[ListNode]:
def getlength(head):
cur=head
length=0
while(cur!=None):
cur=cur.next
length+=1
return length
nn=getlength(head)
dummy=ListNode(next=head)
del_num_front=nn-n
cur=head
if del_num_front==0:
# head=head.next # 这样写其实也行
dummy.next=dummy.next.next
return dummy.next
else:
for i in range(del_num_front-1):
cur=cur.next
cur.next=cur.next.next
return head
看了答案改进后的代码，可以从一开始就用虚拟头结点。
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
#step1: 获取链表长度
cur, length = head, 0
while cur:
length += 1
cur = cur.next
#step2: 找到倒数第N个节点的前面一个节点
cur = dummy
for _ in range(length - n):
cur = cur.next
#step3: 删除节点，并重新连接
cur.next = cur.next.next
return dummy.next
24. 两两交换链表中的结点
题目简述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路
迭代交换
1. 创建哑结点dummyHead，令dummyHead.next=head。
2. 令temp表示当前到达的结点，初始时temp=dummyHead，每次交换temp后面的两个结点
3. 交换之前结点关系temp→node1→node2，交换之后temp→node2→node1
代码如下
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head
temp = dummyHead
while temp.next and temp.next.next:
node1 = temp.next
node2 = temp.next.next
temp.next = node2
node1.next = node2.next # 这一句和下一句不能交换，否则找不到node2.next了
node2.next = node1
temp = node1
return dummyHead.next
142. 环形链表
题目描述 略
思路：
快慢指针法
1. 定义fast和slow指针，fast每次走两步，slow每次走1步
2. 假设head离入口处有a步距离；从入口处到最右侧有b-1个结点，不计算入口处结点，那么从入口处出发，再次回到入口处，需要走k步；如此，链表总计有a+k的结点。
3. 假设slow在离循环入口b步处与fast相遇，那么应该有a+nk+b=2a+2b，a=nk-b，令k=b+c，则有a=c+(n-1)(b+c)，从相遇点到入环点的距离加上n-1圈的环长，恰好等于从链表头部到入环点的距离
4. 因此，当发现slow与fast相遇时，我们在额外使用一个指针ptr。起始，它指向链表头部；随后，它和slow每次向后移动一个单位。最终，它们会在入环点相遇
代码如如下
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。
面试题 02.07. 链表相交
题目描述
给你两个单链表的头结点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。
思路
如这题应该是比较明显的双指针题，要是能实现一种算法让两个指针分别从A和B点往C点走，两个指针分别走到C后，又各自从另外一个指针的起点，也就是A指针第二次走从B点开始走，B指针同理，这样，A指针走的路径长度 AO + OC + BO 必定等于B指针走的路径长度 BO + OC + AO，这也就意味着这两个指针第二轮走必定会在O点相遇，相遇后也即到达了退出循环的条件。
代码如下
# 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:
ta, tb = headA, headB
while ta != tb:
ta = ta.next if ta else headB
tb = tb.next if tb else headA
return tb
总结
1. leetcode里面的头结点貌似就是第一个结点
2. 学会使用快慢指针法
3. 学会面试题中的互补思想
标签：24,head,cur,19,结点,fast,next,链表 From： https://www.cnblogs.com/cp1999/p/17231148.html