思路:
当链表为空或只有一个结点时,则直接返回head;
用一个变量记录当前节点的编号,当编号为奇数时添加到奇数链表,偶数时添加到偶数链表,最后将偶数链表拼接到奇数链表中,返回奇数链表。
复杂度分析:
时间:O(n),遍历一次链表即可
空间:O(1),维护几个必要的指针,是常数级变量空间
import java.util.*;
public class Solution {
public ListNode oddEvenList (ListNode head) {
// write code here
if(head==null || head.next==null)
return head;
int cnt = 1; //记录当前节点的编号
ListNode odd_result = new ListNode(0);//奇数链表的头指针
ListNode odd = odd_result;
ListNode even_result = new ListNode(0);//偶数链表的头指针
ListNode even = even_result;
ListNode p = head;
//遍历链表
while(p!=null){
if((cnt&1)==1){ //奇数编号,入odd链表
odd.next = p;
odd = odd.next;//odd指针右移
} else { //偶数编号,入even链表
even.next = p;
even = even.next;//even指针右移
}
p = p.next;
cnt++;//编号加1
}
even.next = null;//因为偶数链表在后,所以最后要指向null
odd.next = even_result.next;//最后将偶数链表拼接到奇数链表中
return odd_result.next;//完毕
}
}