[数据结构与算法]328. 奇偶链表

力扣打卡:328. 奇偶链表

解题思路

定义一个虚拟的头节点 dummy, 作为偶数节点的开始 head2

给定的头节点 head 作为奇数节点的开始 head1

定义偶数节点的遍历节点 p2, 定义一个奇数节点的遍历节点 p1

定义链表的长度 cnt

如果链表的长度小于3,那么直接返回链表,因为此时的链表已经是奇数偶数分开的状态
对于链表的装填转移,首先是定义一个遍历链表的节点 p

如果是偶数个节点,那么 p 从 head 开始,如果是奇数个节点,那么从 dummy 开始

• p每次走两步
• 偶数节点的下一步是奇数节点的下一步
• 奇数节点的下一步是奇数节点的下一步的下一步
• 然后将偶数遍历节点和奇数遍历节点进行下一步操作
• 判断条件是: 如果偶数节点 or奇数节点为空 || 偶数节点的下一个节点为空 or 奇数节点的下一个节点为空, 那么就跳出这个循环

p = cnt%2==0 ? p1 : p2; // 如果是偶数个节点,那么也就是fast直接到null
while(true){
    p = p.next.next;
    p2.next = p1.next;
    p1.next = p1.next.next;
    p2 = p2.next;
    p1 = p1.next;
    if(p1==null || p2==null || p1.next==null || p2.next==null) break; // 跳出的条件
}

如果是奇数个节点,那么还需要对最后一个的偶数节点进行破环操作

if(p2!=null) { // 进行破环操作
    p2.next = null;
}

最后进行奇偶链表的连接

p = head1;
while(p.next!=null) {
    p = p.next;
}
p.next = head2.next;

代码

/**
 * 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) {
        ListNode dummy = new ListNode(0);// 定义一个虚拟的头节点dummy
        dummy.next = head;
        // 定义偶数头节点,奇数头节点
        // 奇数头节点直接赋值head,偶数头节点因为不确定链表的长度,所以赋值为dummy
        // 如果奇数节点为空了,那么也就是链表的长度为0
        ListNode head1=head,head2=dummy;
        
        // 定义奇数偶数的遍历节点
        ListNode p1=head1,p2=head2;

        // 作为奇数指针,一定是奇数指针先到null,但是当出现了奇数个节点,如果写p1.next.next,会出现空指针异常
        // 定义判断的遍历节点
        int cnt = 0;
        ListNode p = head;
        while(p!=null){
            cnt+=1; // cnt++;
            p=p.next;
        }
        if(head==null||cnt<=2) return head; //如果小于0个,那么跳出,可以直接写cnt<=2
        p = cnt%2==0 ? p1 : p2; // 如果是偶数个节点,那么也就是fast直接到null
        while(true){
        	p = p.next.next;
            p2.next = p1.next;
            p1.next = p1.next.next;
            p2 = p2.next;
            p1 = p1.next;
            if(p1==null || p2==null || p1.next==null || p2.next==null) break; // 跳出的条件
        }
        if(p2!=null) { // 进行破环操作
        	p2.next = null;
        }
        p = head1;
        while(p.next!=null) {
        	p = p.next;
        }
        p.next = head2.next;
        return head1;
    }
}