มี linked list L และค่า k สลับโหนดที่ k จากต้นกับโหนดที่ k จากท้าย คืน linked list ที่แก้ไขแล้ว
ตัวอย่าง: L=[1,5,6,7,1,6,3,9,12], k=3 ผลลัพธ์ [1,5,3,7,1,6,6,9,12] (โหนดที่ 3 จากต้นคือ 6, จากท้ายคือ 3)
วิธีแก้ปัญหา (Two Pointers)
- เดิน
k-1 ก้าวได้firstNode secondNodeเริ่มที่ head, เดินคู่กับtempจนtemp.nextเป็น None- สลับ
firstNode.valกับsecondNode.val
ตัวอย่างโค้ด
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def solve(L, k):
temp = L
for i in range(k-1):
temp = temp.next
firstNode = temp
secondNode = L
while temp.next:
secondNode = secondNode.next
temp = temp.next
firstNode.val, secondNode.val = secondNode.val, firstNode.val
return L
L = [1,5,6,7,1,6,3,9,12]
k = 3
print(solve(make_list(L), k))
อินพุต
[1,5,6,7,1,6,3,9,12], 3
เอาต์พุต
[1, 5, 3, 7, 1, 6, 6, 9, 12]
