（中等）LeetCode 328. 奇偶链表 Java

**奇偶链表**

### 题目描述给定一个单链表的头节点 `head`，将其重新排列为奇数长度链表和偶数长度链表。

链表中每个结点都包含一个整数值 `val`、下一个指针 `next`。

**示例1:**

输入：`[1,2,3,4]`

输出：`[1,3] [2,4]`

**示例2:**

输入：`[-1, -1000,3,99]`

输出：`[-1,3] [-1000,99]`

### 解决方案#### 分析奇偶链表问题要求我们将单链表重新排列为两个链表，一个链表的长度是奇数，另一个链表的长度是偶数。我们可以使用两个指针分别遍历链表，并将奇数长度链表和偶数长度链表分离出来。

#### Java代码

java// Definition for singly-linked list.
public class ListNode {
 int val;
 ListNode next;
 ListNode() {}
 ListNode(int val) { this.val = val; }
 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
 public ListNode oddEvenList(ListNode head) {
 // 检查链表是否为空 if (head == null || head.next == null) return head;

 // 初始化奇数长度链表和偶数长度链表的头结点 ListNode oddHead = head;
 ListNode evenHead = head.next;
 ListNode evenTail = evenHead;

 // 遍历链表，将奇数长度链表和偶数长度链表分离出来 while (evenHead != null && evenHead.next != null) {
 oddHead.next = evenHead.next;
 oddHead = oddHead.next;

 evenHead.next = oddHead.next;
 evenTail = evenHead;
 evenHead = evenHead.next;
 }

 // 将奇数长度链表和偶数长度链表连接起来 oddHead.next = evenHead;

 return head;
 }
}

javapublic static void main(String[] args) {
 // 创建测试链表 ListNode head = new ListNode(1);
 head.next = new ListNode(2);
 head.next.next = new ListNode(3);
 head.next.next.next = new ListNode(4);

 // 测试奇偶链表函数 Solution solution = new Solution();
 ListNode result = solution.oddEvenList(head);

 // 打印结果链表 while (result != null) {
 System.out.print(result.val + " ");
 result = result.next;
 }
}