一,反转链表----LeetCode206
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路
依次遍历链表节点,每遍历一个节点就逆置一个节点,
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *new_head = NULL;//指向新链表头节点的指针
while(head){
ListNode *next = head->next;//备份head->next
head->next = new_head;//更新head->next
new_head = head;//移动new->head
head = next;//遍历链表
}
return new_head;
}
};
二.链表逆序—leetcode92
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路:
第一步,寻找关键节点,包括:逆置段头节点的前驱、逆置前头节点、逆置前尾节点、逆置段尾节点的后继。
第二步,将head向前移动m-1个位置,找到开始逆置的节点,记录该节点的前驱、该节点
第三步,从head开始,逆置n-m+1个节点
第四步,将pre_head与new_head连接,modify_list_tail与head连接
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int change_len = n - m + 1;
ListNode *pre_head = NULL;
ListNode *result = head;
while(head && --m){
pre_head = head;
head = head->next;
}
ListNode *modify_list_tail = head;
ListNode *new_head = NULL;
while(head && change_len){
ListNode *next = head->next;
head->next = new_head;
new_head = head;
head = next;
change_len--;
}
modify_list_tail->next = head;
if (pre_head){
pre_head->next = new_head;
}
else{
result = new_head;
}
return result;
}
};
欢迎关注微信公众号:蛋炒番茄
分享文章、技术、资源!!!
网友评论