首页 > 代码库 > 链表操作 -- 链表自身的处理问题
链表操作 -- 链表自身的处理问题
参考：
http://blog.csdn.net/huangxy10/article/category/1244320这位博友的链表专题
和别人的leetcode代码，在此致谢。
问题：
删除链表中的某个点。
解答：
1）可以借助于节点的前一个节点来删除。
要花费O(n)的时间来查找节点的前继节点。时间复杂度O(n)，空间复杂度O(1).
2）将后一个节点的内容复制到本节点，然后删除后一个节点。时间复杂度O(1),空间复杂度O(1)
这样就省略了查找上一个节点的时间。注意要删除的节点为尾节点的情况！
1 Node* DelNode(Node* node,Node* head) 2 { 3 if(node->next == NULL) 4 { 5 while(head->next != node) 6 head = head->next; 7 8 head->next = NULL; 9 return NULL;10 }else11 {12 *node = *(node->next);13 node->next = node->next->next;14 return node;15 }16 }
问题：
单链表的旋转
解答：
1）每次取得两个相邻的三个节点，反转前两个节点的指针，记录第三个节点。依次往后移动。
时间复杂度：O(n)
空间复杂度：O(1)
1 Node* reverseList(Node* head) 2 { 3 if(head == NULL ||head->next == NULL) 4 return head; 5 6 Node* prev = head; 7 Node* curr = head->next; 8 Node* next; 9 10 prev->next=NULL;11 while(curr != NULL)12 {13 next = curr->next;14 15 curr->next = prev;16 17 prev = curr;18 curr = next;19 }20 21 return prev;22 }
2)使用两个指针，一直指向最左端，一个指向最右端。交换两个指针指向对象的内容，之后左端指针右移，右端指针左移。
耗时操作在于右端指针移动时定位其前一节点的动作。
总体时间复杂度为：O(n2)；空间复杂度为：O(1)
问题：
找出链表中的倒数第n个元素。
类似于 Leetcode -- Remove Nth Node from End of List
解答：
1）两个遍历解决。注意：n大于链表长度的情况。
时间复杂度：O(n)，空间复杂度：O(1)
如何一次遍历就解决问题？
2）使用连个指针【又是双指针！】。选择一个指针向前先走n步，然后两个指针同时移动。当先移动的指针到达链表尾部的时候，另一个指针就指在倒数第n个位置。
时间复杂度：O(n)，空间复杂度：O(1)
1 Node* find_backwark_n(Node* head,int n) 2 { 3 if(n <= 0) 4 return NULL; 5 6 Node* frontNPtr = head; 7 while(n-- && frontNPtr)//这里要注意一点：当最后退出时会判断到n==0,虽然此时会退出while循环，但是n--操作还是会执行，n的值变为了-1 8 frontNPtr = frontNPtr->next; 9 10 //对于n大于链表长度的情况我们返回NULL！11 //如果head == NULL的情况，也会在这里返回12 if(n >= 0)13 return NULL;14 15 Node* backNPtr = head;16 17 while(frontNPtr)18 {19 frontNPtr = frontNPtr->next;20 backNPtr = backNPtr->next;21 }22 23 return backNPtr;24 }
3）借助一个数组来模拟的滑动窗口。窗口的大小为n，窗口在滑动的时候，剔除链表左端的元素，加入右端新元素。
这样当遍历完数组后，窗口中记录的链表中最左端元素即为所求。
时间复杂度：O(n)，空间复杂度：O(m)
1 Node* find_backwark_n(Node* head,int n) 2 { 3 if(n <= 0 || head == NULL) 4 return NULL; 5 6 Node** window = new Node*[n]; 7 if(window==NULL) 8 return NULL; 9 10 Node* curr = head;11 int pos = 0;12 while(curr)13 {14 window[pos % n] = curr;15 16 pos++;17 curr = curr->next;18 }19 20 if(pos < n)21 return NULL;22 23 Node* res = window[pos % n];24 delete window;25 26 return res;27 }
问题：
寻找链表的中间元素。
解答：
1）两次遍历。
2）快+慢指针。
寻找链表的中间元素，也就是寻找链表中位于1/2位置的元素。我们考虑下，寻找链表中1/n位置的元素。
此时仍用快慢指针来处理。只不过快指针每次向前移动n步。
时间复杂度：O(n)，空间复杂度：O(1)
1 Node* get_position(Node* node,int n) 2 { 3 while(n-- && node) 4 node = node->next; 5 if(n >=0) 6 return NULL; 7 8 return node; 9 }10 Node* find_Node(Node* head,int n)11 {12 if(n <= 1)13 return NULL;14 15 Node* fast = get_position(head,n);16 if(fast == NULL)17 return NULL;18 19 Node* slow = head->next;20 while(fast = get_position(fast,n))21 {22 slow = slow->next;23 }24 25 return slow;26 }
问题：
交换链表中”相邻“的节点。只能通过操作节点的next指针来实现。
题目：Leetcode -- Swap Nodes in Pairs
解答：
可以申请使用newHead节点来减少边界判断！
1 ListNode* swapPairs(ListNode *head) 2 { 3 //可以通过使用一个新头来减少对左边界情况的判断 4 ListNode newHead(0); 5 ListNode* p = &newHead; 6 p->next = head; 7 8 //我们在代码中为新的nnext节点连向了nnnext节点 9 //所以不需要处理只剩下单个节点的情况了。10 while(p->next && p->next->next)11 {12 ListNode* n = p->next;13 ListNode* nnn = p->next->next->next;14 15 p->next = p->next->next;16 p->next->next = n;17 p->next->next->next = nnn;18 19 p = p->next->next;20 }21 22 return newHead.next;23 }
问题：
旋转链表n位。 题目： Leetcode -- Rotate List
解答：
1）参考动态窗口的思路。注意窗口为1的情况需要特别处理。
1 int get_length(ListNode* head) 2 { 3 int len = 0; 4 while(head) 5 { 6 len++; 7 head = head->next; 8 } 9 return len;10 }11 12 //使用k的数组存储后[k+1 ~ 2]个值13 //思路来自“寻找单链表中的倒数第n个数”14 ListNode *rotateRight(ListNode *head, int k)15 {16 if(head == NULL)17 return NULL;18 19 k = k % get_length(head);//在使用get_length之前，得确认链表是否为空20 if(k==0)21 return head;22 23 ListNode** window = new ListNode*[k];24 25 ListNode* curr = head;26 int pos = 0;27 while(curr->next)28 {29 window[pos % k] = curr;30 curr = curr->next;31 pos ++ ;32 }33 34 //倒数第k+1个节点被存储在window[pos % (k+1)]中35 //最后一个节点位于curr中36 37 curr->next = head;38 window[pos % k]->next = NULL;39 40 if(k == 1)41 return curr;42 else43 return window[(pos+1) % k];44 }
2）既然归根到底是定位的问题，当然可以用块+慢指针啦
1 int get_length(ListNode* head) 2 { 3 int len = 0; 4 while(head) 5 { 6 len++; 7 head = head->next; 8 } 9 return len;10 }11 12 //快+慢指针啦 ~13 ListNode *rotateRight(ListNode *head, int k)14 {15 if(head == NULL || k<0)16 return NULL;17 if(k == 0)18 return head;19 20 k = k % get_length(head);21 22 ListNode* frontPtr = head;23 while(k--)24 frontPtr = frontPtr->next;25 26 ListNode* backPtr = head;27 while(frontPtr->next)28 {29 frontPtr = frontPtr->next;30 backPtr = backPtr->next;31 }//最终停止时，frontPtr指向最后一个节点，backPtr指向倒数第k+1个节点。32 33 frontPtr->next = head;34 35 head = backPtr->next;36 backPtr->next = NULL;37 38 return head;39 }
可以通过先移动，后判断的方法来减少不必要的就按链表长度。
1 //快+慢指针啦 ~ 2 ListNode *rotateRight(ListNode *head, int k) 3 { 4 if(head == NULL || k<=0) 5 return head; 6 7 ListNode* frontPtr = head; 8 int pos = 0; 9 while(pos < k)10 {11 pos++;12 frontPtr = frontPtr->next;13 if(frontPtr == NULL)14 break;15 }16 17 if(frontPtr == NULL)18 return rotateRight(head,k%pos);19 20 ListNode* backPtr = head;21 while(frontPtr->next)22 {23 frontPtr = frontPtr->next;24 backPtr = backPtr->next;25 }//最终停止时，frontPtr指向最后一个节点，backPtr指向倒数第k+1个节点。26 27 frontPtr->next = head;28 29 head = backPtr->next;30 backPtr->next = NULL;31 32 return head;33 }
链表操作 -- 链表自身的处理问题