這道題一開始想到的方法可能就是patition方法了，大概思路我說一下，先把這個鏈表存為數(shù)組（說明其空間復(fù)雜度為0（1）），然后在對這個數(shù)組進(jìn)行patition，即定義兩個指針，一個指向數(shù)組的-1位置small，一個指向數(shù)組的arr.length位置big，然后來與value比較，比較之后有三種情況：

1. arr[index] < value,這個時候，swap（arr, index++,++small）（主要small要先++再交換，因為其剛開始是-1）

2.arr[index] = value,這個時候，直接index++就行，

3. arr[index] > value 這個時候，swap（arr，index，--big）（主要這里的index不用++）

下面附上源代碼：

public static class Node {
private int value;
private Node next;


public Node(int data) {
this.value = data;
}
}


public static void printLinkedList(Node node) {
System.out.print("LikedList is:");
while (node != null) {
System.out.print(node.value + " "); // 記得是node.value而不是簡單的node
node = node.next;
}
System.out.println();
}


public static Node SmallEqualBig1(Node head, int value) {
if (head == null) { // 如果為空，直接返回head
return head;
}
Node cur = head;
int i = 0;
/* 這里是為了求出鏈表的大小，并將其賦值到數(shù)組中 */
while (cur != null) {
i++;
cur = cur.next;
}
Node nodeArr[] = new Node[i];
cur = head;
i = 0;
while (cur != null) {
nodeArr[i] = cur;
cur = cur.next;
i++;
}
/*
* patition過程，將小于value的值放左邊（small++，index++），將大于value的值放右邊（big--，index不變）,
* 將等于value的值不變（index++）
*/
arrPatition(nodeArr, value);
/* 將patition之后的數(shù)組存到鏈表里面來，這個步驟很重要，要記住 */
for (i = 1; i != nodeArr.length; i++) {
nodeArr[i - 1].next = nodeArr[i];
}
nodeArr[i - 1].next = null;// 這個步驟很容易忘記
return nodeArr[0];// 返回頭鏈表
}


/* 這個過程非常重要，要記住 */
public static void arrPatition(Node nodeArr[], int value) {
int small = -1;
int big = nodeArr.length;
int index = 0;


while (index != big) {
if (value == nodeArr[index].value) {
index++;
} else if (value > nodeArr[index].value) {
swap(nodeArr, ++small, index++);
} else {
swap(nodeArr, --big, index);
}
}
}


public static void swap(Node nodeArr[], int i, int j) {
Node temp = nodeArr[i];
nodeArr[i] = nodeArr[j];
nodeArr[j] = temp;

}

進(jìn)階題目：

其實說到底就是增加兩個條件：

1. 空間復(fù)雜度要為0（1）

2. 穩(wěn)定性要好

其實我個人覺得這種方法實現(xiàn)起來更加容易一點，不信你們可以看一下源代碼：

/* 這種方法空間復(fù)雜度為O（1），其實這種方法更方便，很容易實現(xiàn)，并且b格更高，因為它的穩(wěn)定性比上面的方法好 */
public static Node SmallEqualBig2(Node head, int value) {
/*
* 定義六個指針，分別是smallhead，smalltail，equalhead，equaltail，bighead，bigtail，還有一個next指針
*/
Node sh = null;
Node st = null;
Node eh = null;
Node et = null;
Node bh = null;
Node bt = null;
Node next = null;
/* 一下是主要實現(xiàn)部分，也不難理解 */
while (head != null) {


next = head.next;// 將head.next賦值給next，下面將head.next指向null
head.next = null;
if (head.value < value) {
if (sh == null) {
sh = head;
st = head;
} else {
st.next = head;
st = head;
}
} else if (head.value == value) {
if (eh == null) {
eh = head;
et = head;
} else {
et.next = head;
et = head;
}
} else {
if (bh == null) {
bh = head;
bt = head;
} else {
bt.next = head;
bt = head;
}
}
head = next; // 這一步別忘了，將指針往下面移動，head==null時停止
}


// 連接small部分和equal部分，如果sh！=null就可以連，st.next = eh，
if (st != null) {
st.next = eh;
// 如果中間部分沒有與value相等的元素的話，就將st賦值給et
if (et == null) {
et = st;
}
}


// 連接equal和big部分，如果et！=null就可以連，et.next = bh
if (et != null) {
et.next = bh;
}
// 返回一個鏈表的頭部,判斷small部分==null？，再判斷equal==null？不然就是bh了
if (sh != null) {
return sh;
} else if (eh != null) {
return eh;
} else {
return bh;
}
}
}

總結(jié)

以上是生活随笔為你收集整理的将单向链表按某值划分成左边小、 中间相等、 右边大的形式~迎娶是挺的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。