首页 > 代码库 > leetcode[92] Reverse Linked List II
leetcode[92] Reverse Linked List II
这题和Reverse Node in k-Group相关,主要是看如何翻转一个链表。这里是指定区间从第m个到第n个的翻转例如:
Given 1->2->3->4->5->NULL
, m = 2 and n = 4,
return 1->4->3->2->5->NULL
.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *reverseBetween(ListNode *head, int m, int n) { if (!head || !(head -> next) || m == n) return head; ListNode *pre = new ListNode(0); pre -> next = head; ListNode *mpre = pre; ListNode *nnod = head; while(m-- > 1 && n-- >0) { mpre = mpre -> next; nnod = nnod -> next; } while(n-- > 0) nnod = nnod -> next; // nnod最终是第n个node的下一个节点,用来判断反正的结束标志 ListNode *last = mpre -> next; // 反转相应部分链表 ListNode *cur = last -> next; while(cur != nnod) { last -> next = cur -> next; cur -> next = mpre -> next; mpre -> next = cur; cur = last -> next; } head = pre -> next; delete pre; return head; }};
期间,我试过将nnod就表示第n个节点,然后用cur != nnode->next 来判断终止条件,发现是不行的。为什么呢,因为第n个node已经随着前面处理移到前面去了,所以还是一开始就找到第n个node的下一个作为结束的标志才好。
也可以如下:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *reverseBetween(ListNode *head, int m, int n) { if (!head || !(head -> next) || m == n) return head; ListNode *pre = new ListNode(0); pre -> next = head; ListNode *mpre = pre; ListNode *nnext = head -> next; while(m-- > 1 && n-- > 1) { mpre = mpre -> next; nnext = nnext -> next; } while(n-- > 1) nnext = nnext -> next; ListNode *last = mpre -> next; ListNode *cur = last -> next; while(cur != nnext) { last -> next = cur -> next; cur -> next = mpre -> next; mpre -> next = cur; cur = last -> next; } head = pre -> next; delete pre; return head; }};
leetcode[92] Reverse Linked List II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。