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

Solution:Two pointers in place

Time Complexity: O(N) Space Complexity: O(1)

Solution Code:

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head != null) {

            ListNode odd = head, even = head.next;
            ListNode even_head = even; 

            while (even != null && even.next != null) {
                odd.next = even.next; 
                odd = odd.next;
                even.next = odd.next; 
                even = even.next;
            }
            odd.next = even_head; 
        }
        return head;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 能语音录入吗。不能。 之前从未有过这种感觉。想要在社交软件上倾诉,想要获得关注,总是默默地活着,度过着,直到今天。...
    Gotta717阅读 200评论 0 0