目录
- 1 介绍
- 2 训练
- 3 参考
1 介绍
本博客用来记录代码随想录leetcode200题中链表部分的题目。
2 训练
题目1:203移除链表元素
C++代码如下,
/**
* 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* removeElements(ListNode* head, int val) {
ListNode* p = new ListNode(0, head);
ListNode* res = p;
while (p->next != nullptr) {
if (p->next->val == val) p->next = p->next->next;
else p = p->next;
}
return res->next;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
p = ListNode(0, head)
res = p
while p.next is not None:
if p.next.val == val:
p.next = p.next.next
else:
p = p.next
return res.next
题目2:707设计链表
C++代码如下,
// struct ListNode {
// int val;
// ListNode* next;
// ListNode() : val(0), next(nullptr) {}
// ListNode(int x) : val(x), next(nullptr) {}
// ListNode(int x, ListNode* nx) : val(x), next(nx) {}
// };
class MyLinkedList {
private:
ListNode* head; //head无实际含义
public:
MyLinkedList() {
head = new ListNode(0);
}
int get(int index) {
//时间复杂度O(N)
int i = 0;
ListNode* p = head->next;
while (p != nullptr) {
if (i == index) return p->val;
p = p->next;
i += 1;
}
return -1;
}
void addAtHead(int val) {
//时间复杂度O(1)
ListNode* p = new ListNode(val, head->next);
head->next = p;
}
void addAtTail(int val) {
//时间复杂度O(N)
ListNode* p = head;
while (p->next != nullptr) p = p->next;
ListNode* t = new ListNode(val);
p->next = t;
}
void addAtIndex(int index, int val) {
//时间复杂度O(N)
ListNode* p = head; //p从头结点开始算
int i = 0;
while (p != nullptr && i < index) {
p = p->next;
i += 1;
}
if (p == nullptr) return;
ListNode* t = new ListNode(val, p->next);
p->next = t;
}
void deleteAtIndex(int index) {
//时间复杂度为O(N)
ListNode* p = head; //p从头结点开始算
int i = 0;
while (p != nullptr && i < index) {
p = p->next;
i += 1;
}
if (p == nullptr || p->next == nullptr) return;
p->next = p->next->next;
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
python3代码如下,
class MyLinkedList:
def __init__(self):
self.head = ListNode(0)
def get(self, index: int) -> int:
#时间复杂度为O(N)
i = 0
p = self.head.next
while p is not None:
if i == index:
return p.val
p = p.next
i += 1
return -1
def addAtHead(self, val: int) -> None:
#时间复杂度为O(1)
p = ListNode(val, self.head.next)
self.head.next = p
def addAtTail(self, val: int) -> None:
#时间复杂度为O(N)
p = self.head
while p.next is not None:
p = p.next
t = ListNode(val)
p.next = t
def addAtIndex(self, index: int, val: int) -> None:
#时间复杂为O(N)
p = self.head
i = 0
while p is not None and i < index:
p = p.next
i += 1
if p is None:
return
t = ListNode(val, p.next)
p.next = t
def deleteAtIndex(self, index: int) -> None:
#时间复杂度为O(N)
p = self.head
i = 0
while p is not None and i < index:
p = p.next
i += 1
if p is None or p.next is None:
return
p.next = p.next.next
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
题目3:206. 反转链表
C++代码如下,
/**
* 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* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) { //特判空集或一个结点的时候
return head;
}
ListNode* a = head;
ListNode* b = a->next;
while (a != nullptr && b != nullptr) {
ListNode* t = b->next;
b->next = a;
a = b;
b = t;
}
head->next = nullptr;
return a;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None: #特判空集和一个结点的情况
return head
a = head
b = a.next
while a is not None and b is not None:
t = b.next
b.next = a
a = b
b = t
head.next = None
return a
题目4:24两两交换链表中的节点
C++代码如下,
/**
* 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* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) { //特判空集或者只有一个结点的情况
return head;
}
ListNode* a = head;
ListNode* b = a->next;
ListNode* res = b;
ListNode* aprev = nullptr;
while (a != nullptr && b != nullptr) {
ListNode* t = b->next;
b->next = a;
a->next = t;
if (aprev != nullptr) aprev->next = b;
aprev = a;
a = t;
if (a != nullptr) b = a->next;
else break;
}
return res;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None: #特判空集或者一个结点的情况
return head
a = head
b = a.next
aprev = None
res = b
while a is not None and b is not None:
t = b.next
b.next = a
a.next = t
if aprev is not None:
aprev.next = b
aprev = a
a = t
if a is not None:
b = a.next
else:
break
return res
题目5:19删除链表的倒数第 N 个结点
C++代码如下,
/**
* 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* removeNthFromEnd(ListNode* head, int k) {
//删除倒数第k个结点,快慢指针法
ListNode* dummy = new ListNode(0, head);
ListNode* a = dummy;
ListNode* b = dummy;
while (k--) { //b先走k步
b = b->next;
}
while (b->next != nullptr) { //b走到最后一个结点
a = a->next;
b = b->next;
}
if (a->next != nullptr) a->next = a->next->next;
else cout << "a->next is nullptr!" << endl;
return dummy->next;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
a = dummy
b = dummy
while k > 0:
b = b.next
k -= 1
while b.next is not None:
b = b.next
a = a.next
a.next = a.next.next
return dummy.next
题目6:面试题 02.07. 链表相交
C++代码如下,
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == nullptr || headB == nullptr) { //特判都为空集,或者有一方为空集的情况
return nullptr;
}
ListNode* a = headA;
ListNode* b = headB;
bool flaga = true;
bool flagb = true;
while (a != b) {
a = a->next;
b = b->next;
if (a == nullptr) {
if (flaga) {
a = headB;
flaga = false;
} else {
break;
}
}
if (b == nullptr) {
if (flagb) {
b = headA;
flagb = false;
} else {
break;
}
}
}
if (a == b) return a;
else return nullptr;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA is None or headB is None:
return None
a = headA
b = headB
flaga = True
flagb = True
while a != b:
a = a.next
b = b.next
if a is None:
if flaga:
a = headB
flaga = False
else:
break
if b is None:
if flagb:
b = headA
flagb = False
else:
break
if a == b:
return a
else:
return None
题目7:142. 环形链表 II
C++代码如下,
/**
* 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* a = head;
ListNode* b = head;
while (b != nullptr && b->next != nullptr) {
a = a->next;
b = b->next->next;
//起点到环入口的距离为x
//快慢指针相遇点到环入口的距离为y
//环的周长为c
//有x % c = y恒成立
if (a == b) {
ListNode* t = head;
while (t != a) {
t = t->next;
a = a->next;
}
return a;
}
}
return nullptr;
}
};
python3代码如下,
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
a = head
b = head
while b is not None and b.next is not None:
a = a.next
b = b.next.next
if a == b:
t = head
while t != a:
t = t.next
a = a.next
return a
return None
3 参考
代码随想录官网