【leetcode】328. Odd Even Linked List(奇偶链表)

原文

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

翻译

给定一个单链表,将所有的奇数结点放在偶数结点的前面。注意,我们强调的是结点的位置不是结点的值。

你应该在给定的链表上操作,程序运行的空间复杂度为O(1)。时间复杂度为O(nodes)。

例子:

输入值:1->2->3->4->5->NULL,

返回值:1->3->5->2->4->NULL.

注意:

返回值中偶数和奇数部分结点的相对顺序应该和原始链表中的相对位置一致。

第一个结点被认为是奇数结点,第二个结点被认为是偶数结点,以此类推。

Python代码实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
            
        odd_ptr = head
        even_head = even_ptr = head.next
        
        while(even_ptr and even_ptr.next):
            odd_ptr.next = even_ptr.next
            odd_ptr = odd_ptr.next
            even_ptr.next = odd_ptr.next
            even_ptr = even_ptr.next
                
        odd_ptr.next = even_head
        return head

No comments yet.

Leave a comment

Comment form

All fields marked (*) are required

返回顶部
跳到底部