链表-基础训练（二）链表 day14

两两交换链表中的节点

题目示意：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

原先我的思路是图像上的思路，但是我感觉还是很复杂，

思路1：

原代码：

class ListNode:def __init__(self,data=0,next=None):self.value = dataself.next = next
class MylinkList:def __init__(self):self.dummy_head = ListNode()self.size = 0def addAtHead(self,index:int)->None:self.dummy_head = ListNode(index,self.dummy_head.next)self.size += 1def printList(self)->None:current = self.dummy_headwhile current:print(current.value,end = "->" if current.next else "")current = current.nextprint()def swapList(self)->None:if self.size <= 1:print("元素太少不进行翻转")returnelse:current_1 = self.dummy_head.nextcurrent_2 = current_1.nextcurrent_3 = current_2.nextself.dummy_head.next = current_2current_2.next = current_1current_1.next = current_3for i in range(1,self.size // 2):# 更新指针temp = current_1current_2 = current_3.nextcurrent_1 = current_3current_3 = current_2.next# 交换位置temp.next = current_2current_2.next = current_1current_1.next = current_3# 开始调用函数
obj = MylinkList()
obj.addAthead(1)
obj.addAthead(10)
obj.addAthead(2)
obj.addAthead(3)
obj.addAthead(21)
obj.addAthead(4)
obj.addAthead(33)
obj.printList()
obj.swapList()
obj.printList()

报错：

AttributeError: 'NoneType' object has no attribute 'next'

这个报错主要是因为在current_3的时候很可能是空的，所以我们需要修改代码，同时还有一些其他的错误，主要是对代码的掌控能力还不够：

代码修正：

    def addAtHead(self,index:int)->None:self.dummy_head.next = ListNode(index,self.dummy_head.next)self.size += 1

不可以修改头节点

原代码修改后：

class ListNode:def __init__(self,data=0,next=None):self.value = dataself.next = next
class MylinkList:def __init__(self):self.dummy_head = ListNode()self.size = 0def addAtHead(self,index:int)->None:self.dummy_head.next = ListNode(index,self.dummy_head.next)self.size += 1def printList(self)->None:current = self.dummy_headwhile current:print(current.value,end = "->" if current.next else "")current = current.nextprint()def swapList(self)->None:if self.size <= 1:print("元素太少不进行翻转")return# 使用虚拟头结点简化current_1 = self.dummy_headcurrent_2 = current_1.nextcurrent_3 = current_2.nextwhile current_1.next!=None and current_1.next.next!=None:current_2.next = current_3.nextcurrent_3.next = current_2current_1.next = current_3#交换current_1 = current_3current_2 = current_1.next if current_1 else Nonecurrent_3 = current_2.next if current_2 else None# 开始调用函数
obj = MylinkList()
obj.addAtHead(1)
obj.addAtHead(10)
obj.addAtHead(2)
obj.addAtHead(3)
obj.addAtHead(21)
obj.addAtHead(4)
obj.addAtHead(33)
obj.printList()
obj.swapList()
obj.printList()

思路2：

代码：

class ListNode:def __init__(self,data=0,next=None):self.value = dataself.next = nextclass MylinkList:def __init__(self):self.dummy_head = ListNode()self.size = 0def addAtHead(self,index:int)->None:self.dummy_head.next = ListNode(index,self.dummy_head.next)self.size += 1def printList(self)->None:current = self.dummy_headwhile current:print(current.value,end = "->" if current.next else "")current = current.nextprint()def swapList(self)->None:if self.size <= 1:print("元素太少不进行翻转")returncurrent = self.dummy_headtemp_1 = current.nexttemp_2 = temp_1.nextwhile current.next and current.next.next:temp_1.next = temp_2.nexttemp_2.next = temp_1current.next = temp_2current = temp_2 if temp_2 else Nonetemp_1 = current.next if current else Nonetemp_2 = temp_1.next if temp_1 else None# 开始调用
obj = MylinkList()
obj.addAtHead(1),obj.addAtHead(2),obj.addAtHead(3),obj.addAtHead(10)
obj.addAtHead(15),obj.addAtHead(16),obj.addAtHead(20)
obj.printList()
obj.addAtHead(35)
obj.printList()
obj.swapList()
obj.printList()

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

题目示意：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶思考：

你能尝试使用一趟扫描实现吗？

链表的题建议大家画图来思考：

针对删除的代码：

def deleteN(self,index:int)->None:if index>self.size:print("超出了链表的范围")returnelse:current = self.dummy_headfor i in range(0,index-1):current = current.nextprint(current.next.value)current.next =current.next.nextself.size -= 1

完整的代码：

class ListNode:def __init__(self,data=0,next=None):self.value = dataself.next = nextclass MylinkList:def __init__(self):self.dummy_head = ListNode()self.size = 0def addAtHead(self,index:int)->None:self.dummy_head.next = ListNode(index,self.dummy_head.next)self.size += 1def printList(self)->None:current = self.dummy_head.nextwhile current:print(current.value,end = "->" if current.next else "")current = current.nextprint()def swapList(self)->None:if self.size <= 1:print("元素太少不进行翻转")returncurrent = self.dummy_headtemp_1 = current.nexttemp_2 = temp_1.nextwhile current.next and current.next.next:temp_1.next = temp_2.nexttemp_2.next = temp_1current.next = temp_2current = temp_2 if temp_2 else Nonetemp_1 = current.next if current else Nonetemp_2 = temp_1.next if temp_1 else Nonedef deleteN(self,index:int)->None:if index>self.size:print("超出了链表的范围")returnelse:current = self.dummy_headfor i in range(0,index-1):current = current.nextprint(current.next.value)current.next =current.next.nextself.size -= 1# 开始调用
obj = MylinkList()
obj.addAtHead(1),obj.addAtHead(2),obj.addAtHead(3),obj.addAtHead(10)
obj.addAtHead(15),obj.addAtHead(16),obj.addAtHead(20)
obj.printList()
obj.addAtHead(35)
obj.printList()
obj.swapList()
obj.printList()
obj.deleteN(4)
obj.printList()