主要内容
包含题目：
链表基础知识：
上页的答案：
题目
例1 链表逆序 206 easy
方法一 就地逆置法
方法二 头插法
两种方法的比较
例2 链表中间段逆序 92 medium
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
int reverse_len = n-m+1;
ListNode* pre_head = NULL;
ListNode* result = head;
while(--m){
pre_head = head;
head = head->next;
}
ListNode* modify_tail = head;
ListNode* new_head = NULL;
for(;reverse_len>0;reverse_len--){
ListNode* next = head->next;
head->next = new_head;
new_head = head;
head = next;
}
modify_tail->next = head;
if(pre_head){
pre_head->next = new_head;
}
else{
result = new_head;
}
return result;
}
};
例3 两个排序链表的合并 21 easy
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode temp_head(0);
ListNode* pre = &temp_head;
while(l1&&l2){
if (l1->val<l2->val){
pre->next = l1;
l1=l1->next;
}
else{
pre->next = l2;
l2 = l2->next;
}
pre = pre->next;
}
if(l1){
pre->next = l1;
}
else{
pre->next=l2;
}
return temp_head.next;
}
};
例4 求两个链表的交点 160 easy
方法一 使用set
方法二
方法一 解答（使用set）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include <set>
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
std::set<ListNode*> node_set;
while(headA){
node_set.insert(headA);
headA=headA->next;
}
while(headB){
if(node_set.find(headB)!=node_set.end()){
return headB;
}
headB=headB->next;
}
return NULL;
}
};
方法二 解答（对齐法）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int get_list_length(ListNode* head){
int length = 0;
while(head){
length++;
head = head->next;
}
return length;
}
ListNode* forward_list(int long_len, int short_len, ListNode* head){
int delta = long_len-short_len;
while(head&&delta){
head = head->next;
delta--;
}
return head;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int len_A = get_list_length(headA);
int len_B = get_list_length(headB);
if(len_A>len_B){
headA = forward_list(len_A, len_B,headA);
}
else{
headB = forward_list(len_B,len_A,headB);
}
while(headA){
if(headA==headB){
return headA;
}
headA = headA->next;
headB = headB->next;
}
return NULL;
}
};
例5 链表求环 142 medium（141是判定有没有环，142是判定是否有环并给出换的起始位置）
image.png
方法一 使用set
方法二 快慢指针赛跑
方法一 解答 （使用set）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
#include <set>
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
std::set<ListNode*> node_set;
while(head){
if(node_set.find(head)!=node_set.end()){
return head;
}
node_set.insert(head);
head = head->next;
}
return NULL;
}
};
方法二 解答 （快慢指针赛跑）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
ListNode* meet = NULL;
while(fast){
fast = fast->next;
slow = slow->next;
if(!fast){
return NULL;
}
fast = fast->next;
if(fast==slow){
meet = fast;
break;
}
}
while(head&&meet){
if(head==meet){
return meet;
}
head = head->next;
meet = meet->next;
}
return NULL;
}
};
例5 链表划分 86 medium
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode less_head(0);
ListNode more_head(0);
ListNode* less_ptr = &less_head;
ListNode* more_ptr = &more_head;
while(head){
if(head->val<x){
less_ptr->next = head;
less_ptr = less_ptr->next;
}
else{
more_ptr->next = head;
more_ptr = more_ptr -> next;
}
head = head->next;
}
less_ptr->next = more_head.next;
more_ptr->next = NULL;
return less_head.next;
}
};
例7 复杂链表的深度拷贝 138 hard
例7解答
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
#include <map>
#include <vector>
class Solution {
public:
Node* copyRandomList(Node* head) {
std::map<Node*, int> add_to_num;
std::vector<Node*> num_to_add;
Node* ptr = head;
int i=0;
while(ptr){
num_to_add.push_back(new Node(ptr->val));
add_to_num[ptr]=i;
i++;
ptr = ptr->next;
}
num_to_add.push_back(0);
i=0;
ptr = head;
while(ptr){
num_to_add[i]->next = num_to_add[i+1];
if(ptr->random){
int id = add_to_num[ptr->random];
num_to_add[i]->random = num_to_add[id];
}
i++;
ptr = ptr->next;
}
return num_to_add[0];
}
};
