力扣-86题（Java）-链表双指针

水深无声 2022-10-21 11:59 115阅读 0赞

题目链接：[https://leetcode-cn.com/problems/partition-list/][https_leetcode-cn.com_problems_partition-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210504231414960.png]

/**
     * 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 partition(ListNode head, int x) {
        
            // 思路：分成两个链表small和large，再合并起来
            // smaller和bigger为实际工作指针，head1和head2为总头，代表整个链表
            ListNode smaller=new ListNode(0);
            ListNode bigger=new ListNode(0);
            ListNode head1=smaller,head2=bigger;
    
            while(head!=null){
        
                if(head.val<x){
        
                    smaller.next=head;
                    smaller=smaller.next;
                }else{
        
                    bigger.next=head;
                    bigger=bigger.next;
                }
                head=head.next;
            }
    
            bigger.next=null;
            smaller.next=head2.next;
    
            return head1.next;
    
        }
    }

[https_leetcode-cn.com_problems_partition-list]: https://leetcode-cn.com/problems/partition-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221021/f70cb806145f41fd907b0b2d3ebf7e4e.png
[20210504231414960.png]: /images/20221021/bf03623181ed493db6c0518ce47ed947.png