Leetcode0143--Reorder List 链表重排
2018-07-23 05:31:01来源:博客园 阅读 ()
【转载请注明】https://www.cnblogs.com/igoslly/p/9351564.html
具体的图示可查看 链接
代码一
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if(head==NULL || head->next ==NULL) return; // two pointers split the list // 快慢指针,快指针到尾时,慢指针在前list尾部 // example: 1->2->3->4->5 fast=5,slow=3, 1->2->3 & 4->5 // example: 1->2->3->4 fast=3,slow=2, 1->2 & 3->4 ListNode *slow = head, *fast = head; while(fast->next !=NULL && fast->next->next !=NULL){ slow = slow ->next; fast = fast->next->next; } ListNode *head1 = head; // reverse the second list(with large numbers) // 翻转第二个链表 ListNode *head2 = reverseList(slow->next); slow->next = NULL; while(head2!=NULL){ // list1 size >= list2 size ListNode *next1 = head1->next; ListNode *next2 = head2->next; head1->next = head2; head2->next = next1; head1 = next1; head2 = next2; } if(head1!=NULL){ head1->next = NULL; } } // reverse list ListNode *reverseList(ListNode *head){ if(head==NULL || head->next ==NULL) return head; ListNode * new_head = NULL; while(head!=NULL){ ListNode *pNext = head->next; head->next = new_head; new_head = head; head = pNext; } return new_head; } };
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode* head) { stack<ListNode* > nodestack; int length=0; // 计算链表长度,结点压入stack ListNode *temp = head; while(temp){ length++; nodestack.push(temp); temp = temp->next; } // 栈弹出,连接链表 temp = head; int cnt = length/2; while(cnt){ ListNode *head2 = nodestack.top(); nodestack.pop(); ListNode *headNext = temp->next; temp->next =head2; head2->next = headNext; temp = headNext; cnt--; } // 总数为odd,temp指向末尾元素 // 总数为even,temp会和前元素重复,此处删除 if(length%2){ temp->next = NULL; }else{ temp = NULL; } } };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:秋招复习-C++( 一)
- leetcode 反转链表 2020-06-06
- 数据结构—链表 2020-05-29
- STL之list 2020-04-30
- 单链表 2020-03-31
- DSA_04:链表 2020-03-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash