首页 > 代码库 > 链表系列文章(三)

链表系列文章(三)

上一篇讨论了链表相关的几个有趣的问题,这一篇主要讨论与反转链表有关的问题

基本数据结构:

struct ListNode {    int var;    ListNode *next;    ListNode( int v = 0 ) : var(v), next(NULL) { }};

1.  反转链表

方法一:堆栈法,利用栈后进先出的特性,将链表节点依次入栈,然后弹出并修改next指针

时间复杂度O(n),空间复杂度O(n)

1 ListNode *reverseList(ListNode *head) {2     if(!head || !head->next) return head;3     ListNode newhead(-1), *h = &newhead;4     std::vector<ListNode *> s;5     for( ; head; head = head->next ) s.push_back(head);6     while(!s.empty()) { h->next = s.back(); s.pop_back(); h = h->next; }7     h->next = NULL;8     return newhead.next;9 };

方法二:头插法,创建一个新的头节点,然后遍历链表节点,将每个节点依次插入到头节点后

时间复杂度O(n),空间复杂度O(1)

 1 ListNode *reverseList(ListNode *head) { 2     if(!head || !head->next) return head; 3     ListNode newhead(-1), *h = &newhead, *temp = NULL; 4     while(head) { 5         temp = head->next; 6         head->next = h->next; 7         h->next = head; 8         head = temp; 9     }10     return newhead.next;11 };

方法三:前插法,把链表分为两部分,依次把后一部分的节点前插到前一部分

时间复杂度O(n),空间复杂度O(1)

 1 ListNode *reverseList(ListNode *head) { 2     if(!head || !head->next) return head; 3     ListNode *prev = head, *curr = prev->next, *next = NULL; 4     prev->next = NULL; 5     while(curr) { 6         next = curr->next; 7         curr->next = prev; 8         prev = curr; 9         curr = next;10     }11     return prev;12 };

 

2.  反转链表的[m, n]区间的节点

和反转链表的区别是,我们必须保存反转后的尾指针,使其指向第n+1个节点

方法一:堆栈法,相比上个问题,只需保存一下第n+1个节点地址即可,不再赘述

方法二:头插法,时间复杂度O(n),空间复杂度O(1)

ListNode *reverseList( ListNode *list, int m, int n ) {     ListNode *head = new ListNode();    ListNode *phead = head;    ListNode *curr, *prev;    phead->next = list;    n -= m;//需要反转的次数    while( --m ) { phead = phead->next; } //phead->next指向第m个节点    prev = phead->next;//prev指向反转区间的尾部    curr = prev->next;//指向反转区间的头部    while( n-- ) {         prev->next = curr->next;//这里的prev->next其实就是尾指针!!!        curr->next = phead->next;        phead->next = curr;//头插法        curr = prev->next;      }       return head->next;}   

 

3. 给定两个指针begin和end,反转begin->...->end之间的节点,返回反转后的倒数第一个节点指针

方法参考 2.  反转链表的[m, n]区间的节点

 1 ListNode* reverseList(ListNode *prev, ListNode *begin, ListNode *end) { 2     ListNode *end_next = end->next; 3     for (ListNode *p = begin, *cur = p->next, *next = cur->next; 4         cur != end_next; 5         p = cur, cur = next, next = next ? next->next : NULL) { 6         cur->next = p; 7     } 8     begin->next = end_next;//这里的begin->next其实就是尾指针!!! 9     prev->next = end;10     return begin;11 }

 

4. 小结

反转链表本身比较简单,但是当要区间反转时,一定要牢记,不能忘了尾指针!!!

 

由于本人水平有限,文中难免有不当和错误之处,欢迎大家批评指正,愿共同进步!!!

链表系列文章(三)