LeetCode Top Interview Questions 328. Odd Even Linked List (Java版; Medium)

朴灿烈づ我的快乐病毒、 2023-07-02 05:27 66阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 328. Odd Even Linked List (Java版; Medium) ##

#### 题目描述 ####

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 1:
    
    Input: 1->2->3->4->5->NULL
    Output: 1->3->5->2->4->NULL
    Example 2:
    
    Input: 2->1->3->5->6->4->7->NULL
    Output: 2->3->6->7->1->5->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 ...

#### 第一次做; 最优解, 关键: 循环条件的设置, 这么设置循环条件的原因: 仅用靠后指针的作为边界即可 ####

class Solution { 
        public ListNode oddEvenList(ListNode head) { 
            if(head==null)
                return head;
            ListNode odd=head, even=head.next, evenHead=head.next;
            while(even!=null && even.next!=null){ 
                //change
                odd.next = odd.next.next;
                even.next = even.next.next;
                //update
                odd = odd.next;
                even = even.next;
            }
            //细节: odd不会指向null
            odd.next = evenHead;
            return head;
        }
    }

#### 第一次做; 拆分成两个链表, 一个链表只连接奇数节点, 另一个链表只连接偶数节点. 细节: 需要单独记录技术链表的末尾结点和偶数链表的开头节点 ####

class Solution { 
        public ListNode oddEvenList(ListNode head) { 
            if(head==null || head.next==null || head.next.next==null)
                return head;
            ListNode tmp1 = head;
            ListNode pre1 = null;
            ListNode tmp2 = head.next;
            ListNode head2 = head.next;
            while(tmp1!=null && tmp2!=null){ 
                //change direction
                tmp1.next = tmp1.next.next;
                tmp2.next = tmp2.next==null? null : tmp2.next.next;
                //update
                pre1 = tmp1;
                tmp1 = tmp1.next;
                tmp2 = tmp2.next;
            }
            if(tmp1==null)
                tmp1 = pre1;
            tmp1.next = head2;
            return head;
        }
    }

[welcome to my blog]: https://littlehaes.com