一、题目
二、题解
知识点:双指针
双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个指针(特殊情况甚至可以多个),两个指针或是同方向访问两个链表、或是同方向访问一个链表(快慢指针)、或是相反方向扫描(对撞指针),从而达到我们需要的目的。
思路:
如下图所示,第一个节点是奇数位,第二个节点是偶数,第二个节点后又是奇数位,因此可以断掉节点1和节点2之间的连接,指向节点2的后面即节点3,如红色箭头。如果此时我们将第一个节点指向第三个节点,就可以得到那么第三个节点后为偶数节点,因此我们又可以断掉节点2到节点3之间的连接,指向节点3后一个节点即节点4,如蓝色箭头。那么我们再将第二个节点指向第四个节点,又回到刚刚到情况了。
具体做法:
- step 1:判断空链表的情况,如果链表为空,不用重排。
- step 2:使用双指针odd和even分别遍历奇数节点和偶数节点,并给偶数节点链表一个头。
- step 3:上述过程,每次遍历两个节点,且even在后面,因此每轮循环用even检查后两个元素是否为NULL,如果不为再进入循环进行上述连接过程。
- step 4:将偶数节点头接在奇数最后一个节点后,再返回头部。
import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
//如果链表为空,不用重排
if(head == null)
return head;
//even开头指向第二个节点,可能为空
ListNode even = head.next;
//odd开头指向第一个节点
ListNode odd = head;
//指向even开头
ListNode evenhead = even;
while(even != null && even.next != null){
//odd连接even的后一个,即奇数位
odd.next = even.next;
//odd进入后一个奇数位
odd = odd.next;
//even连接后一个奇数的后一位,即偶数位
even.next = odd.next;
//even进入后一个偶数位
even = even.next;
}
//even整体接在odd后面
odd.next = evenhead;
return head;
}
}