描述
給一個來自已經(jīng)排過序的循環(huán)鏈表的節(jié)點辨宠，寫一個函數(shù)來將一個值插入到循環(huán)鏈表中，并且保持還是有序循環(huán)鏈表背零。給出的節(jié)點可以是鏈表中的任意一個單節(jié)點购岗。返回插入后的新鏈表。
注意事項
3->5->1 是一個循環(huán)鏈表门粪，所以 3 是 1 的下一個節(jié)點喊积。3->5->1 與 5->1->3 相同
樣例
給一個鏈表：3->5->1
插入值 4
返回 5->1->3->4
思路
循環(huán)鏈表的插入要考慮四種情況：
- 鏈表為空
- 鏈表只有一個結(jié)點
- 鏈表值不全部相等時的兩種插入：
a. 順序排列的合適位置
b. 最大值最小值的中間插入- 鏈表值全部相等時，在表頭或表尾的任意插入
代碼
- version1
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param node a list node in the list
* @param x an integer
* @return the inserted new list node
*/
public ListNode insert(ListNode node, int x) {
// 鏈表為空時,新建一個結(jié)點,node.value = x,結(jié)點的next指針指向自己
if (node == null) {
node = new ListNode(x);
node.next = node;
return node;
}
// 在鏈表內(nèi)部尋找合適的插入位置
// current是當前結(jié)點玄妈，node是鏈表頭結(jié)點
ListNode current = node;
ListNode prev = null;
do {
/* prev和current都向后移一位
* 不能寫成prev.next = current;
* 如果是普通鏈表可能問題不大乾吻，但循環(huán)鏈表的話會出問題，
* 因為循環(huán)鏈表實際上就是一個環(huán)形鏈表拟蜻，
* 沒有頭尾绎签，這種情況下給某一個結(jié)點在外面加了一個新的連接結(jié)點，
* 在遍歷循環(huán)鏈表時一定會出現(xiàn)超時
*/
prev = current;
current = current.next;
// 兩種滿足條件的插入情況酝锅，用break結(jié)束循環(huán)
if (x <= current.val && x >= prev.val) {
break;
}
if ((prev.val > current.val) && (x < current.val || x > prev.val)) {
break;
}
// 剛開始current = node,不斷后移,若current再次等于node則證明遍歷整個鏈表一圈
} while (current != node);
// 鏈表內(nèi)部位置都不滿足條件诡必，可以說明鏈表都是值一樣的結(jié)點，直接在邊緣插入
// 創(chuàng)建新結(jié)點搔扁，把新結(jié)點插入到合適的位置
ListNode newNode = new ListNode(x);
newNode.next = current;
prev.next = newNode;
return newNode;
}
}
- version2 不用do while 邏輯更清晰些
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/*
* @param node: a list node in the list
* @param x: An integer
* @return: the inserted new list node
*/
public ListNode insert(ListNode node, int x) {
// 鏈表為空
if (node == null) {
node = new ListNode(x);
node.next = node;
return node;
}
ListNode current = node;
ListNode prev = null;
// 鏈表只有一個結(jié)點
prev = current;
current = current.next;
if (current == node) {
ListNode newNode = new ListNode(x);
current.next = newNode;
newNode.next = current;
}
// 鏈表結(jié)點值不全部相等
// 當鏈表值相等時爸舒，下面的 if 根本不會執(zhí)行
while (current != node) {
if ((prev.val <= x && x <= current.val) ||
(prev.val > current.val && (prev.val < x || x < current.val))) {
ListNode newNode = new ListNode(x);
prev.next = newNode;
newNode.next = current;
break;
}
prev = current;
current = current.next;
}
// 鏈表結(jié)點值全部相等
ListNode newNode = new ListNode(x);
prev.next = newNode;
newNode.next = current;
return node;
}
}
