Python 中的奇偶链表

pythonserver side programmingprogramming更新于 2025/11/23 1:48:17

假设我们有一个单链表，我们必须将所有奇数节点组合在一起，然后是偶数节点。这里我们讨论的是节点位置，而不是节点中的值。我们应该尝试就地完成。因此，如果节点为 [1,22,13,14,25]，则结果将为 [1,13,25,22,14]

要解决这个问题，我们将遵循以下步骤 −

如果 head 为 null 或 head 的下一个为 null，则返回 head
head1 := head, head2 := next of head, head_beg := next of head
当 head2 的下一个不为 null 且 (next of head 不为 null) 的下一个
- next of head1 := next of head2
- next of head2 = next of (next of head)
- head1 := next of head1 且 head2 := next of head2
如果 head2 的下一个不是null
- head1 的下一个 := head2 的下一个
- head1 := head1 的下一个
head1 的下一个 := head2_beg 且 head2 的下一个 = null
返回 head

让我们看看下面的实现以便更好地理解 −

示例

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))