雙向鏈結串列（Doubly Linked List），是一個資料結構，其中每個節點同時擁有指向前一個節點和後一個節點的指針，並可以在任意位置進行插入和刪除操作。因此，雙向鏈結串列不像單向鏈結串列那樣只能從頭到尾或從尾到頭遍歷。
一個雙向鏈結串列節點通常被組織為包含三個元素：
對於第一個節點和最後一個節點，前一個節點指針和後一個節點指針可以為空指針（NULL）。
以下是一個節點的示例：
struct Node {
int value;
Node* prev;
Node* next;
};
舉例：
假設有以下雙向鏈結串列：1 ⇄ 3 ⇄ 5 ⇄ 7，其中 1 是第一個節點，而 7 是最後一個節點。
如果要在第二個節點 3 後插入一個新節點 4，操作流程如下：
插入後，鏈結串列變為：1 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 7。
如果要在第四個節點 5 前插入一個新節點 2，操作流程如下：
插入後，鏈結串列變為：1 ⇄ 2 ⇄ 3 ⇄ 5 ⇄ 7。
如果要從鏈結串列中刪除節點 3，操作流程如下：
刪除後，鏈結串列變為：1 ⇄ 2 ⇄ 5 ⇄ 7。
Doubly linked list是一種常見的資料結構，它與 singly linked list 相似，但每個節點有兩個指向（前一個和後一個）而不是一個。
Doubly linked list的主要優點是可以雙向遍歷列表。這意味著，可以通過列表的前面或後面尋找節點，而不必遞歸或反轉列表。
Doubly linked list需要更多的空間來存儲指向前面節點的指針，這會增加記憶體使用量。
在Doubly linked list中，每個節點都有前一個節點和後一個節點的指針，這使得在插入或刪除節點時可以更加高效。
在Doubly linked list中，頭尾節點的處理需要更多的注意，需要特別處理空列表的情況。
Doubly linked list支持正向和反向遍歷，這使得在某些算法中可以更加高效。
Doubly linked list的插入和刪除操作時需要更多的指針操作，可能比singly linked list要更複雜。
在Doubly linked list中，每個節點都需要額外的空間來存儲前一個節點和後一個節點，這增加了節點的大小，可能會影響效率。
答案:
public void reverse() {
Node temp = null;
Node current = head;
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
if (temp != null) {
head = temp.prev;
}
}
答案:
public DoublyLinkedList merge(DoublyLinkedList list1, DoublyLinkedList list2) {
DoublyLinkedList mergedList = new DoublyLinkedList();
Node temp1 = list1.head;
Node temp2 = list2.head;
while (temp1 != null && temp2 != null) {
if (temp1.value <= temp2.value) {
mergedList.add(temp1.value);
temp1 = temp1.next;
} else {
mergedList.add(temp2.value);
temp2 = temp2.next;
}
}
while (temp1 != null) {
mergedList.add(temp1.value);
temp1 = temp1.next;
}
while (temp2 != null) {
mergedList.add(temp2.value);
temp2 = temp2.next;
}
return mergedList;
}
答案:
public void removeDuplicates() {
if (head == null) {
return;
}
Node current = head;
while (current != null) {
Node temp = current.next;
while (temp != null && temp.value == current.value) {
temp = temp.next;
}
current.next = temp;
temp.prev = current;
current = current.next;
}
}
答案:
public int findKthFromLast(int k) {
Node current = head;
Node runner = head;
for (int i = 0; i < k; i++) {
if (runner == null) {
return -1; // 如果k大於列表的大小，返回-1
}
runner = runner.next;
}
while (runner != null) {
current = current.next;
runner = runner.next;
}
return current.value;
}
答案:
public void sort() {
Node current = head;
Node index = null;
int temp;
if (head == null) {
return;
} else {
while (current != null) {
index = current.next;
while (index != null) {
if (current.value > index.value) {
temp = current.value;
current.value = index.value;
index.value = temp;
}
index = index.next;
}
current = current.next;
}
}
}