LeetCode题解328.odd-even-linked-list

题目地址

https://leetcode.com/problems/odd-even-linked-list/description/

题目描述

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 ...

思路

符合直觉的想法是，先遍历一遍找出奇数的节点。然后再遍历一遍找出偶数节点，最后串起来。

但是有两个问题，如果不修改节点的话，需要借助额外的空间，空间复杂度是 N。如果修改的话，会对第二次遍历（遍历偶数节点）造成影响。

因此可以采用一种做法： 遍历一次，每一步同时修改两个节点就好了，这样就可以规避上面两个问题。

关键点解析

• 用虚拟节点来简化操作

• 循环的结束条件设置为 odd && odd.next && even && even.next, 不应该是odd && even, 否则需要记录一下奇数节点的最后一个节点，复杂了操作

代码

• 语言支持：JS，C++

JavaScript Code:

/*
 * @lc app=leetcode id=328 lang=javascript
 *
 * [328] Odd Even Linked List
 *
 *
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
  if (!head || !head.next) return head;

  const dummyHead1 = {
    next: head
  };
  const dummyHead2 = {
    next: head.next
  };

  let odd = dummyHead1.next;
  let even = dummyHead2.next;

  while (odd && odd.next && even && even.next) {
    const oddNext = odd.next.next;
    const evenNext = even.next.next;

    odd.next = oddNext;
    even.next = evenNext;

    odd = oddNext;
    even = evenNext;
  }

  odd.next = dummyHead2.next;

  return dummyHead1.next;
};

C++ Code：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) return head;
        auto odd = head, evenHead = head->next, even = head->next;
        // 因为“每次循环之后依然保持odd在even之前”，循环条件可以只判断even和even->next是否为空，修改odd和even的指向的操作也可以简化
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

LeetCode题解203.remove-linked-list-elements

题目地址 https://leetcode.com/problems/remove-linked-list-elements/description/ 题目描述 Remove all elements from a linked list of integers that have value val. Example: Input: 1->2->…

LeetCode题解1019.next-greater-node-in-linked-list

题目地址 https://leetcode-cn.com/problems/next-greater-node-in-linked-list/submissions/ 题目描述 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。 每个节点都可能有下一个更大值（next larg…

LeetCode题解206.reverse-linked-list

题目地址 https://leetcode.com/problems/reverse-linked-list/description/ 题目描述 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->…

与在Java中分配数组与分配链表相比，要使用多少内存？ - java

我的猜测是，存储在数组中的每个值都有32位/ 64位字（取决于CPU）。因此它将是数组大小X 32位/ 64位。对于链表，存储指向下一个元素的引用将是链接列表的两倍。因此它将是2 *数组大小X 32位/ 64位。这是正确的，我有什么遗漏吗？ java大神给出的解决方案 多得多。链表中的每个元素都有：指向下一个元素的指针，指向上一个元素的指针，指向项目值的指针…

Python numpy数据指针地址无需更改即可更改 - python

编辑经过一些摆弄之后，到目前为止，我已经隔离了以下状态：一维数组在直接输入变量时提供两个不同的地址，而在使用print()时仅提供一个地址2D数组（或矩阵）在直接输入变量时提供三个不同的地址，在使用print()时提供两个地址3D数组在直接输入变量时提供两个不同的地址，而在使用print()时仅给出一个（显然与一维数组相同）像这样：>>> …