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

1、题目描述

??2、题目分析

【自解法】

奇偶链表模式，可以分别定义不同的链表。

1、设置新的链表头，并且设置奇链表头，偶链表头；

2、设置index链表节点下标，如果 index % 2 == 0 (初始设置index = 0, 则写入奇链表中)，同理，index % 2 ==1 , 则写入偶链表中。

3、最后把链表进行连接起来，即可。

按照这个思路，写出来的代码为：

class Solution {
    public ListNode oddEvenList(ListNode head) {

           ListNode dummy = new ListNode(0,head);
           ListNode odd = new ListNode(-1);
           ListNode odd2 = odd;
           ListNode even = new ListNode(-1);
           ListNode even2 = even;
           int index = 0;
           while(head != null){
               if(index % 2 == 0){
                   odd.next =head;
                   odd = odd.next;
               }else{
                   even.next = head;
                   even= even.next;
               }
               index++;
               head = head.next;
           }
           //进行链表的连接
           dummy.next = odd2.next;
           odd.next = even2.next;
           even.next = null;
           return dummy.next;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n?是链表的节点数。需要遍历链表中的每个节点，并更新指针。

空间复杂度：O(1)。只需要维护有限的指针。

运行结果如下：

?【官方解答】

? ? ? ? 官方解答，比我这个使用的指针少一些，并且没有区分奇偶数下标，而是使用快慢指针模式，这样定义的ListNode可以相对少一些。

实现代码如下：

class Solution {
    public ListNode oddEvenList(ListNode head) {
       //head的非空验证
       if(head == null)
            return null;

       //由于偶数链表涉及到 head.next, 所以必须有 head的非空验证
       ListNode dummy = head.next;
       ListNode odd = head; 
       ListNode even = dummy;
       while(even!=null && even.next !=null){
          odd.next = even.next;
          odd = odd.next;
          even.next = odd.next;
          even = even.next;
       }
       //最后奇链表和偶链表连接
       odd.next = dummy;
       return head;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n?是链表的节点数。需要遍历链表中的每个节点，并更新指针。

空间复杂度：O(1)。只需要维护有限的指针。