1、倒轉單鏈表
非遞歸法
- 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域設為NULL。
2、找出倒數第k個元素(或中間元素）：設置快慢指針
3、刪除環狀單鏈表的一個節點，只給定指向要刪除節點的指針
思路：無法獲取前一個指針，那么可刪除下一個節點，交換當前節點和下一個節點的值即可
4、兩個有序鏈表的合并
歸并即可
5、判斷單鏈表是否有環？環首？
是否有環：快慢指針，如果相遇，說明存在環
環首：可先求出環長。一個圓內的追及問題，兩次相遇時慢指針走過的距離即環長；
此時假設慢指針已走了i步，則快指針已走了2i步；兩個指針同時倒退i步的位置，慢指針退到鏈首，快指針退到i處，則從這兩個位置起，指針各走i步既能在環內相遇。
于是可設置兩個指針，一個在鏈首處，一個在i處，步長為1，第一次相遇的節點即為環首的位置。
6、如何判斷兩個鏈表是否交叉？如果找到交叉點？
思路同5
|