X

LEETCODE 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

说明:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=328

解题思路分析:

本题需要先构造出奇数节点链表,再构建出偶数节点链表,最后将偶数链表追加到奇数链表的尾部即可。

解题时,先取得奇数链表的头节点,即原链表首节点。然后取得偶数链表头结点,即原链表头结点的下一个节点。我们使用递归方式(循环也可以)从奇数链表头结点开始递归,将当前链表的下一个节点指向下下节点,然后再对下下节点进行递归操作。若当前节点的下节点或者下下节点为空时,说明当前节点是链表的尾部,如果当前链表是奇数链表,则将当前节点的下一个节点指向偶数链表的头结点,继续递归操作偶数链表的头结点。如果当前节点是偶数链表的末尾节点,则将当前节点的下一节点设置为空。

实现代码:

ListNode oddHead; // 奇数位首节点
ListNode evenHead; // 偶数位首节点
public ListNode oddEvenList(ListNode head) {
    // 如果头结点为空,返回空
    if(head==null) return null;
    // 奇数位首节点为原链表首节点
    oddHead = head;
    // 偶数位首节点为原链表首节点的下一节点
    evenHead = head.next;
    // 递归奇数位首节点
    help(oddHead,true);
    return oddHead;
}
// node:当前节点
// isOdd:当前节点是否为奇数位
ListNode help(ListNode node, boolean isOdd){
    // 如果当前节点为空,返回空
    if(node==null) return null;
    // 如果当前节点不存在下一节点或者下下节点,当前节点为链表末尾节点
    if((node.next==null||node.next.next==null)){
        // 如果当前是奇数链表,将当前节点的下一节点指向偶数链表首节点
        if(isOdd) node.next=help(evenHead, !isOdd);
        // 如果当前是偶数链表,当前节点的下一节点为空
        else node.next=null;
        // 返回当前节点
        return node;
    }
    // 将当前节点的下一节点设置为下下节点
    node.next = help(node.next.next, isOdd);
    // 返回当前节点
    return node;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Odd Even Linked List.

Memory Usage: 41.7 MB, less than 5.00% of Java online submissions for Odd Even Linked List.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-328-odd-even-linked-list-解题思路分析/
Categories: leetcode
kwantong: