2020.11.13 奇偶链表

2020.11.13 奇偶链表

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例

示例一

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例二

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

说明

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

算法思路

因为考研的专业课时数据结构所以对于这种链表的操作还是比较熟悉的，这类链表问题主要时使用断链的方法，把奇数位的node组成一链，偶数位的node组成一链，然后在连起来。
起始时首先判断这个链表的状态，如果这个链表时空的或者只有1，2个node,那么这个链表时直接符合条件的，不需要调整直接输出就行。如果需要调整，则将node q指向第一个node,node p,p2指向第二位（p2主要时用于后续的链表的链接用），node r指向第三个node（用于拼接符合要求的节点），然后断开p,q的next，其大致状态如下图1。

然后将奇数位的r接到q,偶数位的r接到p,直到r位空指针。

代码实现

public class Nov_13_oddEvenList {
    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }else{
        ListNode q = head;
        ListNode p = head.next;
        ListNode p2 = head.next;
        ListNode r = p.next;
            q.next= null;
            p.next = null;
            while (r != null) {
                if (r != null) {
                    q.next = r;
                    q = r;
                    r = r.next;
                    q.next = null;
                }
                if (r != null) {
                    p.next = r;
                    p = r;
                    r = r.next;
                    p.next = null;
                }
            }
            q.next = p2;
            return head;
        }
    }
    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        ListNode head=listNode;
        for(int i=2;i<10;i++){
            ListNode newnode=new ListNode(i);
            listNode.next=newnode;
            listNode=newnode;
        }
        Nov_13_oddEvenList nov_13_oddEvenList=new Nov_13_oddEvenList();
        head=nov_13_oddEvenList.oddEvenList(head);
        while(head!=null){
            System.out.println(head.val);
            head=head.next;
        }

    }
}


class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

遇到的问题

这个算法的思想其实很简单，没有说明复杂的地方，我在做这个题目的过程中遇到的主要问题是这个head=null和head.next=null的情况没有考虑到。