Giả sử chúng ta có một danh sách L và một giá trị khác k. Chúng ta phải hoán đổi nút thứ k từ đầu và nút thứ k từ cuối và trả về danh sách cuối cùng ở cuối.
Vì vậy, nếu đầu vào giống như L =[1,5,6,7,1,6,3,9,12] k =3, thì đầu ra sẽ là [1,5,3,7,1,6, 6,9,12], nút thứ 3 từ đầu là 6 và từ cuối là 3, vì vậy chúng được đổi chỗ cho nhau.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạm thời:=L
- đối với tôi trong phạm vi từ 0 đến k-2, thực hiện
- temp:=tiếp theo của temp
- firstNode:=temp
- secondNode:=L
- trong khi tiếp theo của tạm thời không null, hãy thực hiện
- secondNode:=next of secondNode
- temp:=tiếp theo của temp
- hoán đổi giá trị của FirstNode và giá trị của secondNode
- trả về L
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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 print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
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_list(solve(make_list(L), k)) Đầu vào
[1,5,6,7,1,6,3,9,12], 3
Đầu ra
[1, 5, 3, 7, 1, 6, 6, 9, 12, ]