首页 > 代码库 > LeetCode: Reverse Linked List
LeetCode: Reverse Linked List
LeetCode: Reverse Linked List
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.
地址：https://oj.leetcode.com/problems/reverse-linked-list-ii/
算法：先找到第m个节点p以及其前趋pre，然后把p记下，因为p是逆置链表部分的最后一个节点。然后从p开始遍历到第n个节点，并把节点依次插入pre后面，注意处理pre为空，也就是m=1的情况。代码：
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(!head) return NULL;13 ListNode *pre = NULL;14 ListNode *p = head;15 int i = 1;16 while(p && i != m){17 pre = p;18 p = p->next;19 ++i;20 }21 if(!p) return head;22 ListNode *first_reverse_node = p;23 if(pre){24 pre->next = NULL;25 }26 ListNode *q = p;27 while(q && i <= n){28 q = p->next;29 if(pre){30 p->next = pre->next;31 pre->next = p;32 }else{33 if(p == head)34 head->next = NULL;35 else{36 p->next = head;37 head = p;38 }39 }40 p = q;41 ++i;42 }43 first_reverse_node->next = q;44 return head;45 }46 };
LeetCode: Reverse Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。