兩兩交換鏈表中的節點

題目示意：

給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

原先我的思路是圖像上的思路，但是我感覺還是很復雜，

思路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()

鏈表相交

給你兩個單鏈表的頭節點?headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點，返回 null 。

圖示兩個鏈表在節點 c1 開始相交：

題目數據 保證 整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

示例 1：

此題暫時留作思考題，希望大家都思考思考