链表分割（解题报告）

刺骨的言语ヽ痛彻心扉 2022-06-15 09:00 155阅读 0赞

## 题目描述 ##

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

给定一个链表的头指针 ListNode\* **pHead**，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

解题思路：用两个链表保存，一个大于等于x的链表，另一个是小于x的链表。最后合并两个链表即可。

注意分支的保存。

package link;
    
    public class Partition {
    
    	public static void main(String [] args){
    		ListNode pHead=new ListNode(6);
    		pHead.next=new ListNode(2);
    		pHead.next.next=new ListNode(8);
    		pHead=partition(pHead,2);
    		while(pHead!=null){
    			System.out.println(pHead.val);
    			pHead=pHead.next;
    		}
    	}
    	
    	
    	public static ListNode partition(ListNode pHead, int x) {
            ListNode large=null;
            ListNode largetail=null;
            ListNode small=null;
            ListNode smalltail=null;
            ListNode current=pHead;
            while(current!=null){
            	if(current.val>=x){
            		if(large==null){
            			large=current;
            			largetail=current;
            		}
            		else{
            			largetail.next=current;
            			largetail=current;
            		}
            	}
            	else {
            		if(small==null){
            			small=current;
            			smalltail=current;
            		}
            		else{
            			smalltail.next=current;
            			smalltail=current;
            		}
            	}
            	current=current.next;
            }
            if(small==null){
            	current=large;
            	largetail.next=null;
            }
            else{
            	current=small;
            	smalltail.next=large;
            	if(large!=null){
            		largetail.next=null;
            	}
            }       
            return current;
        }
    	
    	
    }
    
    
    
    class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }