Giả sử chúng ta có một danh sách liên kết đơn, chúng ta phải gom tất cả các nút ở vị trí lẻ lại với nhau, sau đó là các nút ở vị trí chẵn. Ở đây chúng ta nói về vị trí nút chứ không phải giá trị trong nút. Chúng ta nên thực hiện tại chỗ (in-place). Ví dụ, nếu các nút là [1,22,13,14,25], kết quả sẽ là [1,13,25,22,14].
Để giải quyết, chúng ta làm theo các bước sau:
Nếu head là null hoặc next của head là null, trả về head.
head1 := head, head2 := next của head, head2_beg := next của head.
Khi next của head2 không phải null và next của next của head2 không phải null:
- next của head1 := next của head2.
- next của head2 := next của next của head2.
- head1 := next của head1, head2 := next của head2.
Nếu next của head2 không phải null:
- next của head1 := next của head2.
- head1 := next của head1.
next của head1 := head2_beg và next của head2 = null.
Trả về head.
Ví dụ
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def tao_danh_sach(cac_phan_tu):
head = ListNode(cac_phan_tu[0])
for phan_tu in cac_phan_tu[1:]:
con_tro = head
while con_tro.next:
con_tro = con_tro.next
con_tro.next = ListNode(phan_tu)
return head
def in_danh_sach(head):
con_tro = head
print('[', end="")
while con_tro:
print(con_tro.val, end=", ")
con_tro = con_tro.next
print(']')
class Solution(object):
def oddEvenList(self, head):
if head is None or head.next is None:
return head
head1 = head
head2, head2_beg = head.next, head.next
while head2.next is not None and head2.next.next is not None:
head1.next = head2.next
head2.next = head2.next.next
head1 = head1.next
head2 = head2.next
if head2.next is not None:
head1.next = head2.next
head1 = head1.next
head1.next = head2_beg
head2.next = None
return head
ob1 = Solution()
head = tao_danh_sach([1,22,13,14,25])
in_danh_sach(ob1.oddEvenList(head))
Đầu vào
[1,22,13,14,25]
Đầu ra
[1, 13, 25, 22, 14, ]