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
Constraints:
- 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 ...
- The length of the linked list is between [0, 10^4].
public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null)
return null;
ListNode index = head;
ListNode next = head.next;
ListNode node = head.next;
while (next != null && next.next != null) {
head.next = next.next;
next.next = head.next.next;
head = head.next;
next = next.next;
}
head.next = node;
return index;
}
}- 奇偶链表是index的奇数和偶数不是数字的奇数和偶数，注意审题
- 第一个元素肯定是前面的链表，所以把第一个元素赋值给index
- 第二个元素是头节点的下一个节点，也继续赋值，此时要加一个node节点指向next，否则后面不好链接
- 下面是核心的遍历循环部分，如果next节点以及next的next节点不为空，继续遍历，否则说明节点已经遍历完成了
- 遍历的代码是:
- 头节点的下一节点指向next节点的下一个节点
- next节点的下一个节点指向当前头节点下一节点的下一个节点
- 同时头节点往后移动一个，next节点往后移动一个，继续遍历