Reverse Linked List II -- 翻转部分链表

发布时间:2017-7-1 11:15:11编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Reverse Linked List II -- 翻转部分链表 ",主要涉及到Reverse Linked List II -- 翻转部分链表 方面的内容,对于Reverse Linked List II -- 翻转部分链表 感兴趣的同学可以参考一下。

Reverse Linked List II -- 翻转部分链表

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given1->2->3->4->5->NULL, m = 2 and n = 4,

return1->4->3->2->5->NULL.

Note: 
 Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *reverseBetween(ListNode *head, int m, int n) {12         if(m==n) return head;13         ListNode d(-1);14         ListNode *root=&d;15         root->next=head;16         ListNode *pre=root;17         for(int i=1;i<m;i++){18             pre=pre->next;19         }20         ListNode *head1=pre;21         pre=pre->next;22         ListNode *cur=pre->next;23         for(int i=m;i<n;i++){24             pre->next=cur->next;25             cur->next=head1->next;26             head1->next=cur;27             cur=pre->next;28         }29         return root->next;30     }31 };

这道题是比较常见的链表反转操作,不过不是反转整个链表,而是从m到n的一部分。分为两个步骤,第一步是找到m结点所在位置,第二步就是进行反转直到n结点。反转的方法就是每读到一个结点,把它插入到m结点前面位置,然后m结点接到读到结点的下一个。总共只需要一次扫描,所以时间是O(n),只需要几个辅助指针,空间是O(1)。代码如下: 



上一篇:LeetCode Subsets I& II——递归
下一篇:深度复制

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款