328. 奇偶链表

小咪咪 2023-02-20 13:43 1阅读 0赞

# 题目来源 #

[328. 奇偶链表][328.]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

class Solution {
        
        public ListNode oddEvenList(ListNode head) {
        
            if (head == null || head.next == null || head.next.next == null){
        
                return head;
            }
    
            ListNode odd = head;  // odd指向奇节点的末尾
            ListNode even = head.next; // even指向偶节点的末尾
            while (even != null && even.next != null){
          // 偶数节点之后还有节点没有
                ListNode t = odd.next;  // 临时保存偶节点的开头
                odd.next = even.next;   // 奇节点末尾连接【偶节点】第一个节点
                even.next = even.next.next;    // 偶节点末尾连接【偶节点】第二个节点
                odd.next.next = t;  // 奇数节点--->偶数节点的开头
    
    
                odd = odd.next;
                even = even.next;
            }
    
            return head;
        }
    }

用两个奇偶指针分别指向奇偶节点的起始位置，另外需要一个单独的指针even\_head来保存偶节点的起点位置，然后把奇节点的指向偶节点的下一个(一定是奇节点)，此奇节点后移一步，再把偶节点指向下一个奇节点的下一个(一定是偶节点)，此偶节点后移一步，以此类推直至末尾，此时把分开的偶节点的链表连在奇节点的链表后即可，

/**
     * 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) {
        
            if (head == null || head.next == null || head.next.next == null){
        
                return head;
            }
    
            ListNode odd = head;  // odd指向奇节点的末尾
            ListNode even = head.next; // even指向偶节点的末尾
            ListNode even_head = even;
            while (even != null && even.next != null){
          // 偶数节点之后还有节点没有
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
    
            odd.next = even_head;
    
    
            return head;
        }
    }

![在这里插入图片描述][20200627170259830.png]

[328.]: https://leetcode-cn.com/problems/odd-even-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627170311928.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200627170259830.png]: https://img-blog.csdnimg.cn/20200627170259830.png