算法训练第四天

24. 两两交换链表中的节点

思路：

这个感觉是个模拟类的题目，只要对链表的数据结构熟悉就能做出来

代码：

class Solution(object):def swapPairs(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""if head is None:return headnew_head = ListNode(next=head)pos = new_headwhile pos.next:a = pos.nextb = pos.next.nextif b is None:breaka.next = b.nextb.next = apos.next = bpos = areturn new_head.next

19.删除链表的倒数第N个节点

思路：

这里我选择的算法是统计链表的长度len，然后删除索引为len-n的节点即可。

代码：

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: Optional[ListNode]:type n: int:rtype: Optional[ListNode]"""length = 0pos = headwhile pos :length+=1pos = pos.nextdelet_pos = length-nnew_head = ListNode(next=head)pos = new_headi = 0while i<delet_pos:pos = pos.nexti+=1pos.next = pos.next.nextreturn new_head.next

160.链表相交

思路：

这道题本来打算用两个while循环去暴力搜索的，但是提交的时候超时了，于是改变策略，因为两个链表相交是在后面部分，因此我们只需要获知两个链表的长度，给短的链表在前面补齐长度，然后一起遍历链表，找出相同位置即可。

代码：

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""# 统计两个链表的长度A_len = 0B_len = 0pos = headA while pos !=None:A_len+=1pos = pos.nextpos = headBwhile pos !=None:B_len+=1pos = pos.next# 在短的链表前面补齐while A_len<B_len:new_node = ListNode(0)new_node.next = headAheadA = new_nodeA_len+=1while B_len<A_len:new_node = ListNode(0)new_node.next = headBheadB = new_nodeB_len+=1# 从头遍历两个链表i = headAj = headBwhile i!=None and j!=None:if i==j:return ii = i.nextj = j.next

142.环形链表II

思路：

这道题其实使用python去解很容易实现，只需开一个list记录遍历过的节点，然后每遍历一个节点用in去判断是否在list中，如果在，就把该节点返回即可。

代码：

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""arr = []pos = headwhile pos not in arr and pos:arr.append(pos)pos = pos.nextreturn pos