java单链表的奇偶拆分_leecode--单链表移除链表元素，奇偶链表

落日映苍穹つ 2022-11-10 03:53 120阅读 0赞

移除链表元素

删除链表中等于给定值val的所有节点

示例：

输入: 1->2->6->3->4->5->6, val = 6

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

此问题想着很简单，删除元素必须用到两个节点，一个节点cur用于遍历链表，另一个节点pre表示当前节点的前一个节点。但是还需要注意以下问题：

1)如果需要删除的是链表的头节点该如何处理？

2)如果需要删除的节点是链表中的所有节点如何处理？

3)pre节点和cur节点如何遍历？

一个链表的初始情况：

![bf1c26a374ed1d4caf0923bf4530c817.png][]

需要删除的节点是2，第二步节点情况应该是

![33e765d18c6a13583f6e2665eb2c6209.png][] 可以看出上述情况下，pre节点不用移动，而cur节点移向next即可

如果删除的节点是3，第二步的节点情况应该是

![8a96ecfa88943cb071d8a084bef5661a.png][] 此种情况下，pre节点只想cur，而cur指向本身的next

上述三种情况都处理完成后，则可以轻松写出如下代码。

/\*\*

\* Definition for singly-linked list.

\* public class ListNode \{

\* int val;

\* ListNode next;

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

\* \}

\*/

class Solution \{

public ListNode removeElements(ListNode head, int val) \{

if (null == head) \{

return head;

//删除头节点

while (null != head && head.val == val) \{

if (null != head.next) \{

head = head.next;

\} else \{

head = null;

if (null == head) \{

return head;

ListNode pre = head;

ListNode cur = head.next;

while (null != cur) \{

if (cur.val == val) \{

pre.next = cur.next;

\} else \{

pre = cur;

cur = cur.next;

return head;

奇偶链表

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

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

写完代码后，看了下leecode官网的解答，感觉思路很清晰。就用官网的解答了。

想法

将奇节点放在一个链表里，偶链表放在另一个链表里。然后把偶链表接在奇链表的尾部

算法

这个解法非常符合直觉思路也很简单。但是要写一个精确且没有 bug 的代码还是需要进行一番思索的。 一个 LinkedList 需要一个头指针和一个尾指针来支持双端操作。我们用变量 head 和 odd 保存奇链表的头和尾指针。 evenHead 和 even 保存偶链表的头和尾指针。算法会遍历原链表一次并把奇节点放到奇链表里去、偶节点放到偶链表里去。遍历整个链表我们至少需要一个指针作为迭代器。这里 odd 指针和 even 指针不仅仅是尾指针，也可以扮演原链表迭代器的角色。

![fa21fbf09f35091732ac6cc81cf76b9e.png][] 这个解法非常符合直觉思路也很简单。但是要写一个精确且没有 bug 的代码还是需要进行一番思索的。

代码

/\*\*

\* Definition for singly-linked list.

\* public class ListNode \{

\* int val;

\* ListNode next;

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

\* \}

\*/

class Solution \{

public ListNode oddEvenList(ListNode head) \{

if(null == head || null == head.next)\{

return head;

ListNode oddHead = head;

ListNode evenHead = head.next;

ListNode temp = evenHead;

while(null != evenHead && null != evenHead.next)\{

oddHead.next = evenHead.next;

oddHead = oddHead.next;

evenHead.next = oddHead.next;

evenHead = evenHead.next;

oddHead.next = temp;

return head;

[bf1c26a374ed1d4caf0923bf4530c817.png]: /images/20221023/3e9b72b6bb0a4f8ba2625e71be817de3.png
[33e765d18c6a13583f6e2665eb2c6209.png]: /images/20221023/a4b4e9ad92f84a82bbbc235aecca2a27.png
[8a96ecfa88943cb071d8a084bef5661a.png]: /images/20221023/f51faa6a273d45fe801be1938b80154b.png
[fa21fbf09f35091732ac6cc81cf76b9e.png]: /images/20221023/2e44dfb363ec4553ab7487ece43ac8b0.png