LeetCode刷题【328】奇偶链表

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

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

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode n = head;
        ListNode n2 = head.next;
        ListNode n2head = n2;
        while (true) {
            if (n2.next != null) {
                n.next = n2.next;
                n = n.next;
                if (n.next != null) {
                    n2.next = n.next;
                    n2 = n2.next;
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        n2.next=null;
        n.next = n2head;
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

        解答成功:
        执行耗时:0 ms,击败了100.00% 的Java用户
        内存消耗:38.2 MB,击败了18.05% 的Java用户

借助n，n2构建奇偶链表，每次从head向后移动2位，第一个是奇数位，第二个是偶数位，判断好有没有下一个的情况。在不断迭代循环中，依次建立新的关联关系。

同时因为n，n2是不断向后迭代遍历的，需要借助一个n2head来保存偶数位的链表头，最终有个n2.next=null;切断偶数位再链接回原来他后一位的奇数位的关联关系。再此时n为奇数位的末位，next指向之前创建的偶数位链表的首位。

重新捋下代码，把while中的两个if条件提到while条件中，那么两个break分支就可以去掉了。这边可能会有疑虑，如果n.next!=null而n2.next=null的情况，会被错误的跳过，但是实际情况是这个分支场景会被下面的n.next = n2head覆盖替换掉，所以无需担心。同样的n2.next=null要处理的切断环链的操作会在while循环里被n2.next = n.next;处理掉。

最终优化过的代码

//leetcode submit region begin(Prohibit modification and deletion)


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode n = head;
        ListNode n2 = head.next;
        ListNode n2head = n2;
        while (n.next != null && n2.next != null) {
                n.next = n2.next;
                n = n.next;
                n2.next = n.next;
                n2 = n2.next;
        }
        n.next = n2head;
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

提交结果

        解答成功:
        执行耗时:0 ms,击败了100.00% 的Java用户
        内存消耗:37.8 MB,击败了93.06% 的Java用户