leetcode 328 奇偶链表

leetcode 第328题 奇偶链表

题目要求

首先题目要求 在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题，那么就限制了不能创建一个n个节点的数组来解决问题，所以只能通过移动指针的方式解题

思路

我们可以定义三个指针(cur、next、flag)，第一个指针(cur)指向链表的第一个节点，第二个(next)和第三个指针(flag)指向链表的第二个节点，第三个指针是为了让我们在移动完指针之后还能找到链表的第二个节点。

然后我们可以将链表第一个节点指向第三个节点，第二个节点指向第四个节点，完成之后将cur和next指针指向第三个节点和第四个节点，以此类推， 等到其中某个指针指向的节点为null的时候就说明链表走到尽头了，然后终止循环，将cur节点的next指向一开始链表的第二个节点，这也是为什么要在一开始保存链表第二个节点，为了就是现在能够找到该节点

如图

// 循环体中做的第一步  移动奇位数的指针
    cur.next = cur.next.next;
    cur = cur.next;

// 循环体中做的第二步  移动奇位数的指针
    next.next = next.next.next;
    next = next.next;

循环结束之后各个指针的指向

通过第三张图片可以明显看到 我们只需要将cur指针指向链表的第二个节点，也就是我们一开始保存的flag节点即可

代码

function oddEvenList(head: ListNode | null): ListNode | null {
  if (head == null) {
    return null;
  }
  if (head.next == null) {
    return head;
  }
  let cur: ListNode = head;
  let next: ListNode = head.next;
  let falg: ListNode = head.next;
  while (cur.next && next.next) {
    cur.next = cur.next.next;
    cur = cur.next;
    next.next = next.next.next;
    next = next.next;
  }
  cur.next = falg;
  return head;
}