1、倒轉(zhuǎn)單鏈表
非遞歸法
- struct Node
- {
- int data;
- Node * next;
- }
- void reverse(Node*& head) {
- if (head == NULL) {
- return;
- }
- Node * pre, * cur, * nxt;
- pre = head;
- cur = head -> next;
- while (cur != NULL) {
- pre = cur -> next;
- pre = cur;
- cur = nxt;
- nxt = nxt -> next;
- }
- head -> next = NULL;
- head = pre;
- }
遞歸法
- Node * reverse(Node * node, Node *&head)
- {
- if (node == NULL || node -> next == NULL) {
- head = node;
- return;
- }
- else {
- Node * nxt = reverse(node -> next, head)
- node = nxt -> next;
- return node;
- }
- }
- 最后要將返回的node的next域設(shè)為NULL。
2、找出倒數(shù)第k個(gè)元素(或中間元素）：設(shè)置快慢指針
3、刪除環(huán)狀單鏈表的一個(gè)節(jié)點(diǎn)，只給定指向要?jiǎng)h除節(jié)點(diǎn)的指針
思路：無法獲取前一個(gè)指針，那么可刪除下一個(gè)節(jié)點(diǎn)，交換當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的值即可
4、兩個(gè)有序鏈表的合并
歸并即可
5、判斷單鏈表是否有環(huán)？環(huán)首？
是否有環(huán)：快慢指針，如果相遇，說明存在環(huán)
環(huán)首：可先求出環(huán)長(zhǎng)。一個(gè)圓內(nèi)的追及問題，兩次相遇時(shí)慢指針走過的距離即環(huán)長(zhǎng)；
此時(shí)假設(shè)慢指針已走了i步，則快指針已走了2i步；兩個(gè)指針同時(shí)倒退i步的位置，慢指針退到鏈?zhǔn)祝熘羔樛说絠處，則從這兩個(gè)位置起，指針各走i步既能在環(huán)內(nèi)相遇。
于是可設(shè)置兩個(gè)指針，一個(gè)在鏈?zhǔn)滋?，一個(gè)在i處，步長(zhǎng)為1，第一次相遇的節(jié)點(diǎn)即為環(huán)首的位置。
6、如何判斷兩個(gè)鏈表是否交叉？如果找到交叉點(diǎn)？
思路同5
|