題目描述：
撰寫代碼，以給定值x為基準將鏈表分割成兩部分，所有小于x的節點排在大于或等于x的節點之前，給定一個鏈表的頭指標ListNode* pHead,請回傳重新排列后的鏈表的頭指標，注意：分割以后保持原來的資料順序不變，
示例描述：
x=12,原鏈表如下：
兩個線段存放節點程序：
分割后的鏈表如下：
個人理解：
- 本題用兩個線段來存放比x小的節點和大于等于x的節點，剛開始的時候兩個線段的頭尾bs,be;as,ae;先置為null
- 定義一個cur,在原來的鏈表中進行遍歷
- 如果cur.val<x,那么將該節點放到第一個線段，否則放到第二個線段，如果第一個線段沒有資料，那么直接回傳as;如果第一個線段有資料，那么將be和as進行拼接，be.next = as，
- 當cur為null的時候，原來的單鏈表就遍歷完了
題解實作：
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode bs = null;//將兩段的首尾先置為null
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
while(cur!= null){
if(cur.val < x){//再分為第一次插入以及不是第一次插入
if(bs==null){//第一次插入
bs = cur;
be = cur;
}else{//不是第一次插入,就進行尾插法
be.next = cur;
be = be.next;
}
}else {//同樣的也再分為第一次插入以及不是第一次插入
if(as == null){//第一次插入
as = cur;
ae = cur;
}else{//不是第一次插入
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//1.判斷bs是否為null,如果bs==null，則回傳as
if(bs == null){
return as;
}
//2.如果bs不為null，需要進行拼接
be.next = as;
//3.如果ae不為null，那么ae的next需要置為null,此時回傳bs
if(ae!=null){
ae.next = null;
}
return bs;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292492.html
標籤：其他
下一篇：面試招聘——計算機網路專場（一）