Giả sử chúng ta có một danh sách được liên kết đơn lẻ, chúng ta phải nhóm tất cả các nút lẻ lại với nhau theo sau là các nút chẵn. Ở đây chúng ta đang nói về vị trí nút chứ không phải giá trị trong các nút. Chúng ta nên cố gắng làm điều đó tại chỗ. Vì vậy, 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 vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu phần đầu là rỗng hoặc phần tiếp theo của phần đầu là rỗng, thì trả về phần đầu
- head1:=head, head2:=next of head, head_beg:=next of head
- while next of head2 không phải là null và next of (next of head không phải là null)
- next of head1:=next of head2
- next of head2 =next of (tiếp theo của head)
- head1:=next of head1 và head2:=next of head2
- nếu phần tiếp theo của head2 không rỗng
- next of head1:=next of head2
- head1:=next of head1
- tiếp theo của head1:=head2_beg và tiếp theo của head2 =null
- quay lại đầu
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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(']')
class Solution(object):
def oddEvenList(self, head):
if head == None or head.next ==None:
return head
head1=head
head2,head2_beg= head.next,head.next
while head2.next!= None and head2.next.next!= None:
head1.next = head2.next
head2.next = head2.next.next
head1 = head1.next
head2 = head2.next
if head2.next!=None:
head1.next = head2.next
head1 = head1.next
head1.next = head2_beg
head2.next = None
return head
ob1 = Solution()
head = make_list([1,22,13,14,25])
print_list(ob1.oddEvenList(head)) Đầu vào
[1,22,13,14,25]
Đầu ra
[1, 13, 25, 22, 14, ]