鏈表結(jié)束篇：鏈表的五種常見操作
- 單鏈表翻轉(zhuǎn)
- 檢測一個鏈表中是否有環(huán)
- 兩個有序的鏈表合并
- 刪除鏈表倒數(shù)第 n 個結(jié)點(diǎn)
- 求鏈表的中間結(jié)點(diǎn)
更新一下 五苍凛、 的思路
規(guī)則界限就是：
快指針走的長度(鏈表長度 + null) = 快length = length + 1
快指針先走 n + 1
然后慢指針 和 快指針一起走，當(dāng)快指針走到 快length 時
慢指針走到：
快length - (n + 1) = length + 1 - (n + 1) = length - n
第 (length - n) 位置就是倒數(shù)第(n + 1)個結(jié)點(diǎn)。
一庐氮、單鏈表翻轉(zhuǎn)
在 判斷回文串 這篇筆記中有詳細(xì)記錄独悴，此處只列舉代碼了述吸。
/**
* 鏈表的反轉(zhuǎn)可以想象成摸石頭過河那個游戲
* 兩只腳配上三塊磚頭就可以前進(jìn)了
* <p>
* 每次循環(huán)做的事：
* ①第一塊磚頭的next改變
* ②三塊磚頭前移一個位置
*
* @return 反轉(zhuǎn)后的單鏈表
*/
public SingleLinked<E> reverse() {
Node<E> realHead = first;
//無結(jié)點(diǎn)
if (realHead == null) {
return this;
}
Node<E> temp = realHead.getNext();
//只有一個頭結(jié)點(diǎn)
if (temp == null) {
return this;
}
Node<E> flag = temp.getNext();
//把realHead與其下一個結(jié)點(diǎn)的連接斷開
realHead.setNext(null);
//一次循環(huán)盏求，只改變一個結(jié)點(diǎn)的指針反轉(zhuǎn)
//剩下就是temp flag 等引用的變化
while (flag != null) {
temp.setNext(realHead);
realHead = temp;
temp = flag;
flag = flag.getNext();
}
temp.setNext(realHead);
first = temp;
return this;
}
二噪漾、檢測一個鏈表中是否有環(huán)
思路：使用快慢指針充活，快指針每次循環(huán)比慢指針多走一步蜂莉，這樣當(dāng)快指針走到 null 時蜡娶，慢指針走了一半， 若鏈表中有環(huán)（尾結(jié)點(diǎn)的后繼指針指向了鏈表中的某一結(jié)點(diǎn)）映穗，那么 快指針 永遠(yuǎn)不會為 null窖张，但是會出現(xiàn) 快指針與慢指針 指向同一結(jié)點(diǎn)的情況，以此來判斷一個單鏈表是否有環(huán)蚁滋。
image
畫這個圖好累宿接。。辕录。
public boolean hasCircle() {
Node<E> fast = first;
Node<E> slow = first;
while (fast != null && fast.getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
if (fast == slow) {
//說明有環(huán)睦霎，fast追到了 slow
return true;
}
}
return false;
}
三、兩個有序的鏈表合并
思路：若兩個鏈表都是升序鏈表踏拜。
取兩個鏈表（A,B）的頭結(jié)點(diǎn)比較誰兴橛：將小的作為新鏈表的頭結(jié)點(diǎn)。假設(shè) B 小速梗，接下來比較 B的頭結(jié)點(diǎn).next 與 A 的頭結(jié)點(diǎn)誰小肮塞，小的作為新鏈表的頭結(jié)點(diǎn)的 next。
image
可以使用遞歸解決此類問題：
import bean.Node;
import exception.CannotControlException;
import exception.UnorderedLinkedException;
/**
* @author : zyf
* @since : 2018-12-28 15:55
**/
public class SingleLinkedUtil {
private static final int ASC = 0;
private static final int DES = 1;
private static final int NULL_LINKED = 2;//表示空鏈表
private static final int UNORDERED = -1;
/**
* 判斷鏈表是否有序
* @param linked
* @return 是升序還是降序
*/
public static int isOrderLinked(SingleLinked<Integer> linked){
Node<Integer> first = linked.getFirst();
if(first == null){
return NULL_LINKED;
}
Node<Integer> next = first.getNext();
//0 表示升序
//1 表示返序
int flag = UNORDERED;
while (next != null){
if(next.getT() >= first.getT()){
//大于 則 flag 為0
if(flag == UNORDERED){
//說明是第一次判斷
flag = ASC;
}else {
if(flag != ASC){
//說明在循環(huán)中的某一次將 flag 的值改為 1 了
//說明不是一個有序鏈表
return UNORDERED;
}else {
first = next;
next = next.getNext();
}
}
}else {
//小于 則 flag 為 1
if(flag == -1){
flag = DES;
}else {
if(flag != DES){
return UNORDERED;
}else {
first = next;
next = next.getNext();
}
}
}
}
return flag;
}
public static SingleLinked<Integer> mergeOrderedLinked(SingleLinked<Integer> a,SingleLinked<Integer> b){
//先判斷 a,b 是否有序
int aOrder = SingleLinkedUtil.isOrderLinked(a);
int bOrder = SingleLinkedUtil.isOrderLinked(b);
if(aOrder == NULL_LINKED){
return b;
}
if(bOrder == NULL_LINKED){
return a;
}
SingleLinked<Integer> result = new SingleLinked<Integer>();
if(aOrder != UNORDERED && bOrder != UNORDERED){
if(aOrder != bOrder){
//說明兩者的排序方式不一樣
throw new CannotControlException();
}else {
if(aOrder == ASC){
//說明兩個鏈表都是升序
//通過遞歸的方式合并兩個鏈表
result.addLast(mergeASC(a.getFirst(), b.getFirst()));
}else {
//說明兩個鏈表都是降序
result.addLast(mergeDES(a.getFirst(), b.getFirst()));
}
}
}else {
throw new UnorderedLinkedException();
}
return result;
}
/**
* 合并升序鏈表
* @param nodeA
* @param nodeB
* @return
*/
private static Node<Integer> mergeASC(Node<Integer> nodeA,Node<Integer> nodeB){
Node<Integer> result;
if(nodeA == null){
return nodeB;
}
if(nodeB == null){
return nodeA;
}
if(nodeA.getT() < nodeB.getT()){
result = nodeA;
result.setNext(mergeASC(nodeA.getNext(),nodeB));
}else {
result = nodeB;
result.setNext(mergeASC(nodeA,nodeB.getNext()));
}
return result;
}
/**
* 合并降序鏈表
* @param nodeA
* @param nodeB
* @return
*/
private static Node<Integer> mergeDES(Node<Integer> nodeA,Node<Integer> nodeB){
Node<Integer> result;
if(nodeA == null){
return nodeB;
}
if(nodeB == null){
return nodeA;
}
if(nodeA.getT() > nodeB.getT()){
result = nodeA;
result.setNext(mergeDES(nodeA.getNext(),nodeB));
}else {
result = nodeB;
result.setNext(mergeDES(nodeA,nodeB.getNext()));
}
return result;
}
}
四姻锁、刪除單鏈表倒數(shù)第 n 個結(jié)點(diǎn)
這個好難枕赵，網(wǎng)上找到的答案能看懂，知道會得到正確的結(jié)果位隶，但是如何表述思考過程好難拷窜。
image
public void removeAtFromEnd2(int n) {
if (n <= 0) {
throw new UnsupportedOperationException("n必須大于0");
}
int length = 0;
Node<E> temp = this.first;
while (temp != null) {
temp = temp.getNext();
length++;
}
if(n > length){
throw new LinkedOutOfBoundsException();
}
int target = length - n;
Node<E> again = this.first;
if(target == 0){
//要移除第一個
this.first = again.getNext();
}
while (target > 1) {
again = again.getNext();
target--;
}
again.setNext(again.getNext().getNext());
}
五、刪除單鏈表倒數(shù)第 n 個結(jié)點(diǎn)（使用快慢指針的方式解決問題）
image
/**
* 為什么最后從 0 開始移動的涧黄？
* 自己可以運(yùn)行測試一下篮昧，如果要刪除的是鏈表的頭結(jié)點(diǎn)
* 那么從 頭結(jié)點(diǎn)前開始移動，代碼會更優(yōu)化
*
* @param n
*/
public void removeAtFromEnd(int n) {
if (n <= 0) {
throw new UnsupportedOperationException("n必須大于0");
}
Node<E> beforeFirst = new Node<>();
beforeFirst.setNext(first);
//現(xiàn)在快慢指針都在 0 位置呢（如果假設(shè)頭結(jié)點(diǎn)為 1 ）
Node<E> fast = beforeFirst;
Node<E> slow = beforeFirst;
//開始移動 fast 直到到達(dá) size - n 的位置
while (fast != null && n > -1) {
fast = fast.getNext();
n--;
}
if (n > -1) {
//說明要刪除的位置超過了鏈表的長度
throw new LinkedOutOfBoundsException();
}
//當(dāng) fast 處于 n 的位置的時候
//再讓 slow 與 fast 一起移動
//這樣當(dāng) fast 移動到鏈表尾部 fast==null 為 true 時
//slow 正好移動到 size - n 的位置
while (fast != null) {
fast = fast.getNext();
slow = slow.getNext();
}
slow.setNext(slow.getNext().getNext());
}
六笋妥、求鏈表的中間結(jié)點(diǎn)
這個和第 二 道題很像懊昨，都是使用快慢指針來解決問題。
快指針從頭結(jié)點(diǎn)每次循環(huán)走兩步春宣。
慢指針從頭結(jié)點(diǎn)每次循環(huán)走一步酵颁。
當(dāng)快指針走到null時，慢指針剛好走到鏈表中間結(jié)點(diǎn)月帝。
若鏈表長度為奇數(shù)：慢指針是中間結(jié)點(diǎn)躏惋。
若鏈表長度為偶數(shù)：慢指針是上中結(jié)點(diǎn)，慢指針.next 是下中結(jié)點(diǎn)嚷辅。
[1,2,3,4,5,6,7,8] ：上中結(jié)點(diǎn)：4 下中結(jié)點(diǎn)：5
/**
* 使用快慢指針即可拿到中間結(jié)點(diǎn)
* 快指針比慢指針多走一步即可
*
* @return
*/
public Node<E> getMiddleNode() {
if (first == null) {
throw new EmptyLinkedException();
}
Node<E> fast = first;
Node<E> slow = first;
while (fast.getNext() != null && fast.getNext().getNext() != null) {
fast = fast.getNext().getNext();
slow = slow.getNext();
}
return slow;
}
