两两交换链表中的节点
题目示意：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
原先我的思路是图像上的思路，但是我感觉还是很复杂，
思路1：
原代码：
class ListNode:
def __init__(self,data=0,next=None):
self.value = data
self.next = next
class MylinkList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def addAtHead(self,index:int)->None:
self.dummy_head = ListNode(index,self.dummy_head.next)
self.size += 1
def printList(self)->None:
current = self.dummy_head
while current:
print(current.value,end = "->" if current.next else "")
current = current.next
print()
def swapList(self)->None:
if self.size <= 1:
print("元素太少不进行翻转")
return
else:
current_1 = self.dummy_head.next
current_2 = current_1.next
current_3 = current_2.next
self.dummy_head.next = current_2
current_2.next = current_1
current_1.next = current_3
for i in range(1,self.size // 2):
# 更新指针
temp = current_1
current_2 = current_3.next
current_1 = current_3
current_3 = current_2.next
# 交换位置
temp.next = current_2
current_2.next = current_1
current_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 = data
self.next = next
class MylinkList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def addAtHead(self,index:int)->None:
self.dummy_head.next = ListNode(index,self.dummy_head.next)
self.size += 1
def printList(self)->None:
current = self.dummy_head
while current:
print(current.value,end = "->" if current.next else "")
current = current.next
print()
def swapList(self)->None:
if self.size <= 1:
print("元素太少不进行翻转")
return
# 使用虚拟头结点简化
current_1 = self.dummy_head
current_2 = current_1.next
current_3 = current_2.next
while current_1.next!=None and current_1.next.next!=None:
current_2.next = current_3.next
current_3.next = current_2
current_1.next = current_3
#交换
current_1 = current_3
current_2 = current_1.next if current_1 else None
current_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 = data
self.next = next
class MylinkList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def addAtHead(self,index:int)->None:
self.dummy_head.next = ListNode(index,self.dummy_head.next)
self.size += 1
def printList(self)->None:
current = self.dummy_head
while current:
print(current.value,end = "->" if current.next else "")
current = current.next
print()
def swapList(self)->None:
if self.size <= 1:
print("元素太少不进行翻转")
return
current = self.dummy_head
temp_1 = current.next
temp_2 = temp_1.next
while current.next and current.next.next:
temp_1.next = temp_2.next
temp_2.next = temp_1
current.next = temp_2
current = temp_2 if temp_2 else None
temp_1 = current.next if current else None
temp_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("超出了链表的范围")
return
else:
current = self.dummy_head
for i in range(0,index-1):
current = current.next
print(current.next.value)
current.next =current.next.next
self.size -= 1完整的代码：
class ListNode:
def __init__(self,data=0,next=None):
self.value = data
self.next = next
class MylinkList:
def __init__(self):
self.dummy_head = ListNode()
self.size = 0
def addAtHead(self,index:int)->None:
self.dummy_head.next = ListNode(index,self.dummy_head.next)
self.size += 1
def printList(self)->None:
current = self.dummy_head.next
while current:
print(current.value,end = "->" if current.next else "")
current = current.next
print()
def swapList(self)->None:
if self.size <= 1:
print("元素太少不进行翻转")
return
current = self.dummy_head
temp_1 = current.next
temp_2 = temp_1.next
while current.next and current.next.next:
temp_1.next = temp_2.next
temp_2.next = temp_1
current.next = temp_2
current = temp_2 if temp_2 else None
temp_1 = current.next if current else None
temp_2 = temp_1.next if temp_1 else None
def deleteN(self,index:int)->None:
if index>self.size:
print("超出了链表的范围")
return
else:
current = self.dummy_head
for i in range(0,index-1):
current = current.next
print(current.next.value)
current.next =current.next.next
self.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()链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
此题暂时留作思考题，希望大家都思考思考