力扣-328题（Java）-链表的双指针法

悠悠 2022-10-06 02:57 159阅读 0赞

题目链接：[https://leetcode-cn.com/problems/odd-even-linked-list/][https_leetcode-cn.com_problems_odd-even-linked-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]

/**
     * 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) {
        
            //tip:
            //当处理链表中，思路中需要分成两类进行时，考虑双指针法
            
            ListNode odd=new ListNode(0);//奇数位置
            ListNode even=new ListNode(0);//偶数位置
    
            ListNode p=odd;//双指针
            ListNode q=even;
            
            if(head==null||head.next==null) return head;//链表为空链表或只有一个节点
            
            while(head!=null&&head.next!=null){
        //节点数>=2个
                odd.next=head;
                odd=odd.next;
                System.out.println(head.val);//用于后台打印，不影响提交结果
    
                even.next=head.next;
                even=even.next;
    
                head=head.next.next;
            }
    
            if(head!=null) {
        //链表中节点数为奇数个，如 1 2 3 4 5 null，最终head为5
                odd.next=head;
                odd=odd.next;
                even.next=null;
                odd.next=q.next;
            }
            else{
        //链表中节点数为偶数个，如 1 2 3 4 null，最终head为null
                even.next=head;
                odd.next=q.next;
            }
            
            return p.next;
            
        }
    }

[https_leetcode-cn.com_problems_odd-even-linked-list]: https://leetcode-cn.com/problems/odd-even-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221005/9a64ddbaf7c7439f935a29a40fdca6e7.png