328. Odd Even Linked List

题目描述和难度

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

  请尝试使用原地算法完成。你的算法的空间复杂度应为 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

  说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
• 题目难度：中等。
• 英文网址：328. Odd Even Linked List 。
• 中文网址：328. 奇偶链表 。

思路分析

求解关键：给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes为节点总数。题目要求原地算法完成，那么就一定得“穿针引线”了。

• 思路1：可以使用 LeetCode 第 86 题题解思路 2 完成。
• 思路2：同样使用两个指针，一次跳过一个节点完成“穿针引线”，特别注意要一些边界情况的判断。

参考解答

参考解答1

Java 写法：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }

    public ListNode(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("arr can not be empty");
        }
        this.val = nums[0];
        ListNode curr = this;
        for (int i = 1; i < nums.length; i++) {
            curr.next = new ListNode(nums[i]);
            curr = curr.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        ListNode cur = this;
        while (cur != null) {
            s.append(cur.val + " -> ");
            cur = cur.next;
        }
        s.append("NULL");
        return s.toString();
    }
}

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummyNodeOdd = new ListNode(-1);
        ListNode dummyNodeEven = new ListNode(-1);
        ListNode curOdd = dummyNodeOdd;
        ListNode curEven = dummyNodeEven;
        int count = 0;
        while (head != null) {
            if (count % 2 == 0) {
                curOdd.next = head;
                curOdd = curOdd.next;
            } else {
                curEven.next = head;
                curEven = curEven.next;
            }
            head = head.next;
            count++;
        }
        curOdd.next = dummyNodeEven.next;
        // 特别注意：最后这一步不能忘记，否则会产生一个循环链表
        curEven.next = null;
        return dummyNodeOdd.next;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = new ListNode(nums);
        Solution solution = new Solution();
        ListNode oddEvenList = solution.oddEvenList(head);
        System.out.println(oddEvenList);
    }
}

参考解答2（推荐）

• 注意1：我们采用一次跳过一个节点“穿针引线”的办法来完成这个问题；
• 注意2：在 while 循环体中，如果结点个数是奇数的话，偶数索引的最后一个元素的 next 指针会指向一个 null （因为跳过一个结点改变 next 指针的操作是一起进行的），这一点完全可以分类讨论，因为就两种情况，如下图所示：

public class Solution2 {

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode oddHead = head;
        ListNode evenHead = head.next;

        ListNode oddCur = oddHead;
        ListNode evenCur = evenHead;
        // 执行循环的条件不能写错
        while (evenCur != null && evenCur.next != null) {
            oddCur.next = oddCur.next.next;
            evenCur.next = evenCur.next.next;

            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        oddCur.next = evenHead;
        return oddHead;
    }
}

参考解答2（推荐）

• 注意1：我们采用一次跳过一个节点“穿针引线”的办法来完成这个问题；
• 注意2：在 while 循环体中，如果结点个数是奇数的话，偶数索引的最后一个元素的 next 指针会指向一个 null （因为跳过一个结点改变 next 指针的操作是一起进行的），这一点完全可以分类讨论，因为就两种情况，如下图所示：

public class Solution2 {

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode oddHead = head;
        ListNode evenHead = head.next;

        ListNode oddCur = oddHead;
        ListNode evenCur = evenHead;
        // 执行循环的条件不能写错
        while (evenCur != null && evenCur.next != null) {
            oddCur.next = oddCur.next.next;
            evenCur.next = evenCur.next.next;

            oddCur = oddCur.next;
            evenCur = evenCur.next;
        }
        oddCur.next = evenHead;
        return oddHead;
    }
}

Python 写法：

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head is None or head.next is None:
            return head

        # odd 奇数
        odd_head = head
        even_head = head.next

        odd_cur = odd_head
        even_cur = even_head

        while even_cur and even_cur.next:
            odd_cur.next = odd_cur.next.next
            even_cur.next = even_cur.next.next

            odd_cur = odd_cur.next
            even_cur = even_cur.next

        odd_cur.next = even_head
        return odd_head

思路概述：

在遍历的过程中，标记奇数节点和偶数节点，把奇数节点和偶数节点分开。最后把奇数节点的最后一个节点指向偶数节点的开始节点，具体细节请见代码。

我的解答：

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode oddHead = head;
        ListNode evenHead = oddHead.next;
        ListNode oddNode = oddHead;
        ListNode evenNode = evenHead;
        ListNode currentNode = evenHead.next;
        boolean isodd = true;
        while (currentNode != null) {
            if (isodd) {
                oddNode.next = currentNode;
                oddNode = currentNode;
            } else {
                evenNode.next = currentNode;
                evenNode = currentNode;
            }
            isodd = !isodd;
            currentNode = currentNode.next;
        }
        isodd = !isodd;
        if (isodd) {
            oddNode.next = evenHead;
            evenNode.next = null;
        } else {
            oddNode.next = evenHead;
        }
        return oddHead;
    }


    public static void main(String[] args) {
        ListNode node1 = createListNode(new int[]{1, 2, 3, 4, 5});
        Solution solution = new Solution();
        ListNode result1 = solution.oddEvenList(node1);
        printLinkedList(result1);

        System.out.println("------");


        ListNode node2 = createListNode(new int[]{1, 2, 3, 4});
        ListNode result2 = solution.oddEvenList(node2);
        printLinkedList(result2);

        System.out.println("------");


        ListNode node3 = createListNode(new int[]{1, 2});
        ListNode result3 = solution.oddEvenList(node3);
        printLinkedList(result3);
    }

    public static ListNode createListNode(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        ListNode head = new ListNode(nums[0]);
        ListNode curNode = head;
        for (int i = 1; i < nums.length; i++) {
            curNode.next = new ListNode(nums[i]);
            curNode = curNode.next;
        }
        return head;
    }

    // 超级简单的一个工具方法
    public static void printLinkedList(ListNode head) {
        ListNode curNode = head;
        while (curNode != null) {
            System.out.printf("%s\t", curNode.val);
            curNode = curNode.next;
        }
        System.out.printf("null");
    }
}

网友的解答：http://blog.csdn.net/guicaisa/article/details/50557475 显然，网友的解法会更简洁一些： 根据网友的解答自己写了一遍：

public class Solution2 {

    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode oddNode = head;
        ListNode evenNode = head.next;
        ListNode evenHead = evenNode;
        while (evenNode != null && evenNode.next != null) {
            oddNode.next = evenNode.next;
            oddNode = oddNode.next;
            evenNode.next = oddNode.next;
            evenNode = evenNode.next;
        }
        oddNode.next = evenHead;
        return head;
    }


    public static void main(String[] args) {
        ListNode node1 = createListNode(new int[]{1, 2, 3, 4, 5});
        Solution2 solution = new Solution2();
        ListNode result1 = solution.oddEvenList(node1);
        printLinkedList(result1);

        System.out.println("------");


        ListNode node2 = createListNode(new int[]{1, 2, 3, 4});
        ListNode result2 = solution.oddEvenList(node2);
        printLinkedList(result2);

        System.out.println("------");


        ListNode node3 = createListNode(new int[]{1, 2});
        ListNode result3 = solution.oddEvenList(node3);
        printLinkedList(result3);
    }

    public static ListNode createListNode(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        ListNode head = new ListNode(nums[0]);
        ListNode curNode = head;
        for (int i = 1; i < nums.length; i++) {
            curNode.next = new ListNode(nums[i]);
            curNode = curNode.next;
        }
        return head;
    }

    // 超级简单的一个工具方法
    public static void printLinkedList(ListNode head) {
        ListNode curNode = head;
        while (curNode != null) {
            System.out.printf("%s\t", curNode.val);
            curNode = curNode.next;
        }
        System.out.printf("null");
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0328-odd-even-linked-list ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。