首页 > 代码库 > 【leetcode】Reverse Linked List II
【leetcode】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:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
思路：
首先把指针移动到第m个元素
然后计算需要交换的元素个数，n-m
每次交换时，把下一个元素交换到需要交换的初始位置
如
1->2->3->4->5->NULL
找到交换位置
1->2->3->4->5->NULL
把下一个元素交换到需要交换的初始位置
1->3->2->4->5->NULL
继续交换
1->4->3->2->5->NULL
注意初始位置在开头时，每次交换都要更新head
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 13 14 ListNode *p1=head;15 ListNode *p1Pre=new ListNode(0);16 17 int k=n-m;18 19 p1Pre->next=p1;20 21 ListNode *needDelete=p1Pre;22 23 while(m-1>0)24 {25 p1Pre=p1;26 p1=p1->next;27 m--;28 }29 30 31 while(k>0)32 {33 ListNode* cur=p1->next;34 p1->next=cur->next;35 36 if(p1Pre->next==head)37 {38 head=cur;39 }40 41 cur->next=p1Pre->next;42 p1Pre->next=cur;43 44 k--;45 }46 47 delete needDelete;48 return head;49 }50 };
【leetcode】Reverse Linked List II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。