鏈表（單鏈表）是一種通過指標將一組零散的記憶體塊串聯起來的資料結構，每個鏈表的結點除了存盤的資料之外，還需要記錄鏈上的下一個節點的地址
-
鏈表的插入和洗掉（給定節點指標）時間復雜度O(1)，但遍歷洗掉的時間復雜度是O(n)
-
雙向鏈表：每個結點不止有一個后繼指標指向后面的結點，還有一個前驅指標指向前面的結點，在洗掉指定指標指向的節點時，時間復雜度僅為O(1)若鏈表是有序鏈表，那么查找時可以向前向后遍歷，平均能少遍歷一半的資料
-
鏈表有關演算法
-
單鏈表反轉
定義兩個節點curr，pre，curr.next指向pre，然后curr、pre后移一位，重復直到最后一個節點，? -
檢測環
1.快慢指標，快指標每次走兩步，慢指標每次走一步，?相遇則說明有環
2.遍歷鏈表并將節點值加入散串列中，若有重復的說明有環? -
有序鏈表合并
定義一個哨兵，每次加入較小節點，最后加入較長鏈表剩余部分 -
洗掉倒數第k個節點
定義快慢指標，從頭節點開始快指標先走k-1步，然后快慢同時走，快指標走到表尾時慢指標指向的就是倒數第k個 -
求中間節點
快慢指標，快指標每次兩步慢指標每次一步，快指標走到表尾慢指標指向中間節點 -
判斷回文
快慢指標找到中點，慢指標移動程序中同時反轉鏈表，然后從中點至兩端一起移動并判斷
-
鏈表Java實作
public class myLinkedlist {
public Node head;
public myLinkedlist() {
head = new Node(-1);
}
/**
* 將data加到鏈表尾部
*
* @param data
* @return
*/
public boolean append(int data) {
Node iter = head;
while (iter.next != null) iter = iter.next;
iter.next = new Node(data);
return true;
}
/**
* 將value插入到index之后
*
* @param index
* @return
*/
public boolean insertAfter(int index, int value) {
Node iter = head;
while (iter.data != index && iter.next != null) iter = iter.next;
if (iter.data != index && iter.next == null) {
System.out.println("鏈表中無對應節點！");
return false;
}
Node temp = iter.next;
iter.next = new Node(value);
iter.next.next = temp;
return true;
}
public boolean delete(int index) {
Node iter = head;
while (iter.next != null && iter.next.data != index) iter = iter.next;
if (iter.data != index && iter.next == null) {
System.out.println("鏈表中無對應節點！");
return false;
}
Node temp = iter.next.next;
iter.next = temp;
return true;
}
/**
* 反轉鏈表
*/
public void reverse() {
Node iter = head.next;
if (iter.next == null)
return;
Node pre = iter;
Node mid = iter.next;
Node after = mid.next;
pre.next = null;
//after為null時說明mid是最后一個
while (after != null) {
//每次將mid指向pre
mid.next = pre;
pre = mid;
mid = after;
after = after.next;
}
mid.next = pre;
head.next = mid;
}
public boolean isPalindrome() {
if (head.next == null) {
System.out.println("鏈表為空！");
return false;
}
//只有兩個節點
if (head.next.next.next == null) {
int first = head.next.data;
int second = head.next.next.data;
if (first == second)
return true;
else
return false;
}
Node fast;//快指標
Node slow;//慢指標
fast = slow = head.next;
int fStep;//快指標步數
int sStep;//慢指標步數
fStep = sStep = 0;
while (fast.next != null) {
fast = fast.next;
fStep++;
}
sStep = fStep / 2;
//慢指標向前移動，同時將單鏈表反轉
Node pre, mid, after;
pre = slow;
mid = slow.next;
after = mid.next;
slow.next = null;
while (sStep > 0) {
mid.next = pre;
pre = mid;
mid = after;
after = after.next;
sStep--;
}
Node toStart, toEnd;
//奇數遍歷起點
if (fStep % 2 == 1) {
toStart = pre;
toEnd = mid;
}
//偶數遍歷起點
else {
toStart = pre.next;
toEnd = mid;
}
do {
if (toStart.data != toEnd.data)
return false;
toStart = toStart.next;
toEnd = toEnd.next;
} while (toStart != null && toEnd != null);
return true;
}
public String toString() {
StringBuilder builder = new StringBuilder();
Node iter = head;
int size = 0;
while (iter.next != null) {
builder.append(iter.next.data + ",");
size ++;
iter = iter.next;
}
return builder.toString() + "\t(size: " + size + ")";
}
public void linkedlistTest(){
myLinkedlist test = new myLinkedlist();
test.append(1);
System.out.println(test.toString());
test.delete(1);
System.out.println(test.toString());
test.append(2);
System.out.println(test.toString());
test.insertAfter(1,3);
System.out.println(test.toString());
test.delete(2);
System.out.println(test.toString());
test.append(4);
test.append(5);
test.append(6);
System.out.println(test.toString());
test.reverse();
System.out.println(test.toString());
test.reverse();
System.out.println(test.toString());
//測驗是否為回文串
test.append(1);
test.append(2);
test.append(3);
test.append(2);
test.append(1);
System.out.println(test.isPalindrome());
}
}
class Node {
int data;
Node next;
protected Node(int data) {
this.data = https://www.cnblogs.com/codespoon/p/data;
this.next = null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31074.html
標籤：其他
上一篇：Wireless Network POJ - 2236
下一篇：4.排序（上）