Believing Process 力扣328.奇偶链表

题干:

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
public class 奇偶链表 {
    public static void main(String[] args) {
        int[] nums ={1,2,3,4,5};
        ListNode head = createList(nums);
        ListNode ans = oddEvenList(head);
        while(ans!=null) {
            System.out.println(ans.val);
            ans = ans.next;
        }
    }
    public static ListNode oddEvenList(ListNode head) {
       if(head == null)
           return head;
       ListNode odd = head,even = head.next,evenHead = even;
       while(even!=null&&even.next!=null){
           odd.next = odd.next.next;
           odd = odd.next;
           even.next = even.next.next;
           even = even.next;
       }
       odd.next=evenHead;
       return head;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public static ListNode createList(int[] nums){
        ListNode head = new ListNode();
        ListNode point = head;
        for(int i:nums){
            ListNode newNode = new ListNode(i);
            point.next= newNode;
            point = newNode;
        }
        return head.next;
    }
}

         odd 奇数, even 偶数。

        大致思路是让处于odd位置的结点连接起来,再让处于even位置的结点连接起来,然后让最后一个odd结点的next指向even结点的头节点。

上一篇:b_lc_心算挑战(排序+贪心)


下一篇:Codeforces Round #650 (Div. 3)