一:两数之和

image-20250929150424064

1. 暴力

不写

2. 哈希表

哈希表通过用空间换时间,使用哈希函数将任意长度的键转换为一个固定范围的数组下标,时间复杂度为O(1)O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashMap;
for(int i = 0; i < nums.size(); ++i)
{
auto it = hashMap.find(target - nums[i]); // 返回迭代器
if(it != hashMap.end()) // 和尾后迭代器比对
{
return {it->second, i}; // 找到就返回下标
}
hashMap[nums[i]] = i; // 没找到就把数据添加进hash表
}
return {};
}
};
1
2
3
4
5
6
7
8
9
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashMap = dict()
for i, num in enumerate(nums): # 遍历
if target - nums[i] in hashMap: # 是否存在,可把nums[i]改为num
return [hashMap[target - num], i]
hashMap[nums[i]] = i
return []

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>(); // 初始化一个哈希表
for( int i = 0; i < nums.length; ++i)
{
if(hashMap.containsKey(target - nums[i])) // 这里的K大写
{
return new int[]{hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[0]; // 返回为空
}
}

image-20250929160013307

二:移动零

image-20250929162440339

1. 双指针

题目要求不能复制,同时保证原有序列的顺序不变,因此只能交换非零值和零值的位置。

  • 思路一:处理零值,将零和右边非零值进行交换
  • 思路二:处理非零值,将非零值和左边零值进行交换

方式一需要不断寻找非零值,性能稍差,因此采用方式二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int Left = 0, Right = 0; // Left的左边均为非零值,其指向第一个零值。Right的右边为未处理的序列,当前指向用于判断零值和非零值
for (int i = 0; i < nums.size(); ++i)
{
if (nums[i])
{
swap(nums[Left], nums[Right]); // 交换位置
++Left;
}
++Right;
}
}
};
1
2
3
4
5
6
7
8
9
10
11
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
Left = Right = 0
for num in nums:
if num:
nums[Left], nums[Right] = nums[Right], nums[Left]
Left += 1
Right += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public void moveZeroes(int[] nums) {
int Left = 0;
int Right = 0;
int temp;
for (int i = 0; i < nums.length; ++i)
{
if (nums[i] != 0)
{
temp = nums[Left];
nums[Left] = nums[Right];
nums[Right] = temp;
++Left;
}
++Right;
}
}
}

image-20250929171149413

三:相交链表

1. Hash表

将其中一个链表的数据放入哈希表,第二个链表依次判断是否包含即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode *> hashTalble;
while (headA)
{
hashTalble.insert(headA);
headA = headA->next;
}
while (headB)
{
if (hashTalble.count(headB))
{
return headB;
}
headB = headB->next;
}
return nullptr;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
hashTable = set()
while headA:
hashTable.add(headA)
headA = headA.next # 使用.运算符不是->,非指针

while headB:
if headB in hashTable:
return headB
headB = headB.next
return None # 空为None


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> hashTable = new HashSet<ListNode>();
while (headA != null) // 不能直接判断headA
{
hashTable.add(headA);
headA = headA.next; // 使用.
}

while (headB != null)
{
if (hashTable.contains(headB))
{
return headB;
}
headB = headB.next;
}
return null; // 使用null
}
}

image-20250929214103239

2. 双指针

使用两个指针指向两个链表的头结点,判断两个指针是否相等,走到末尾如果两者不相同则将指针赋值为另一个链表的头结点继续遍历,如果有相交结点,在不超过第二次遍历一定会在相交结点使两个指针相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
if (!pA || !pB)
{
return nullptr;
}
while (pA != pB)
{
if (pA == nullptr) pA = headB; // 可用三元运算符替代
else pA = pA->next;

if (pB == nullptr) pB = headA;
else pB = pB->next;
}
return pA;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
if not headA or not headB:
return None
pA = headA
pB = headB
while pA != pB: # 也可以用is not
if not pA: # 或if pA is None:
pA = headB
else:
pA = pA.next
if not pB:
pB = headA
else:
pB = pB.next
return pA
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null)
return null;
ListNode pA = headA, pB = headB;
while (pA != pB)
{
pA = (pA == null) ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}

image-20250929223144815

四:反转链表

image-20250929234228521

image-20251001225201451

1. 迭代反转

根据头结点可获取到下一个结点,头结点的先前结点为空,可依次遍历将当前结点的指向进行反转,题目要求输出的结果也是反转的,因此需要返回最后一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr;
ListNode *next = nullptr;
ListNode *cur = head;
while (cur)
{
next = cur->next; // 先拿到后继结点
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
ListNode cur = head;
while (cur != null)
{
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
1
2
3
4
5
6
7
8
9
10
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre

image-20251001230612457

2. 递归反转

依次传入下一个结点,并返回最后一个结点,与上一个解法的区别在于由后向前反转,此时不需要前继结点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) // 链表为空或只有单结点
{
return head;
}
ListNode *Last = reverseList(head->next); // 最后一个结点在这里
head->next->next = head; // 这里不能用Last,因为Last不动,而head一直向前
head->next = nullptr; // 必须设为空,否则第一个结点和第二个结点将互指
return Last; // 一直返回最后一个结点
}
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
{
return head;
}
ListNode Last = reverseList(head.next);
head.next.next = head;
head.next = null;
return Last;
}
}
1
2
3
4
5
6
7
8
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
Last = self.reverseList(head.next) // 这里要用self
head.next.next = head
head.next = None
return Last

image-20251001234501412

五:回文链表

image-20251002130355108

1. 数组

将链表中的数据复制到数组中,然后将数组反转或遍历第一个和最后一个数据进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vals;
while (head)
{
vals.emplace_back(head->val);
head = head->next;
}
for (int i = 0, j = static_cast<int>(vals.size() - 1); i < j; ++i, --j)
{
if (vals[i] != vals[j]) return false;
}
return true;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
while (head != null)
{
vals.add(head.val);
head = head.next;
}
for (int i = 0, j = vals.size() - 1; i < j; ++i, --j)
{
if (vals.get(i) != vals.get(j)) return false;
}
return true;
}
}
1
2
3
4
5
6
7
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
vals = []
while head:
vals.append(head.val)
head = head.next
return vals == vals[::-1] # 可直接利用反转列表来比对

image-20251002134301939

2. 递归

递归可以从后往前遍历,但是也需要从前往后的一个结点来进行对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
ListNode *frontIteration = nullptr; // 从前往后
public:
bool isPalindrome(ListNode* head) {
frontIteration = head;
return recursion(frontIteration);
}
bool recursion(ListNode* head)
{
if (head)
{
if (!recursion(head->next)) // false继续返回false
{
return false;
}
if (head->val != frontIteration->val) return false; // true则进行比对
frontIteration = frontIteration->next; // 每一层向后遍历
}
return true; // 末尾返回true
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private ListNode frontIteration = null;
public boolean isPalindrome(ListNode head) { // boolean非bool
frontIteration = head;
return recursion(head);
}
public boolean recursion(ListNode head)
{
if (head != null)
{
if (!recursion(head.next))
{
return false;
}
if (head.val != frontIteration.val) return false;
frontIteration = frontIteration.next;
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
self.frontIteration = head # 成员变量的初始化,如果不在这里需要在__init__中
return self._recursion(head)
def _recursion(self, head: Optional[ListNode]) -> bool: # _表明内部使用,Optional表示可能的类型,-> bool返回类型
if head:
if not self._recursion(head.next):
return False
if head.val != self.frontIteration.val:
return False
self.frontIteration = self.frontIteration.next
return True

image-20251002142637198

3.快慢指针

该方法主要是寻找到链表的中间结点,然后将前半部分或者后半部分反转,对两部分进行比较,由于中间需要修改链表,并发处理下需要锁定其他线程或进程对链表的访问。快慢的意思则是通过两个指针,一个步长为2,另一个为1,当快指针到达尾节点时,慢指针到达中间结点,从而减少重复遍历的时间。反转可以使用之前的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head) return true;
ListNode *lastNode = reverseList(interMediateNode(head));
while (head != lastNode && head != nullptr)
{
if (head->val != lastNode->val) return false;
head = head->next;
lastNode = lastNode->next;
}
return true;
}
// 寻找中间节点,
ListNode* interMediateNode(ListNode* head)
{
ListNode *fastNode = head;
ListNode *slowNode = head;
while (fastNode != nullptr && fastNode->next->next != nullptr)
{
fastNode = fastNode->next->next;
slowNode = slowNode->next;
}
return slowNode;
}

ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr;
ListNode *next = nullptr;
ListNode *cur = head;
while (cur)
{
next = cur->next; // 先拿到后继结点
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public boolean isPalindrome(ListNode head) { // boolean非bool
if (head == null) return true;
ListNode lastNode = reverseList(interMediateNode(head));
while (head != lastNode && head != null)
{
if (head.val != lastNode.val) return false;
head = head.next;
lastNode = lastNode.next;
}
return true;
}

public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
ListNode cur = head;
while (cur != null)
{
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}

public ListNode interMediateNode(ListNode head)
{
ListNode fastNode = head;
ListNode slowNode = head;
while (fastNode != null && fastNode.next.next != null)
{
fastNode = fastNode.next.next;
slowNode = slowNode.next;
}
return slowNode;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if (not head):
return True
lastNode = self.reverseList(self.interMediateNode(head))
while (head != lastNode and head):
if head.val != lastNode.val:
return False
head = head.next
lastNode = lastNode.next
return True

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
pre = None
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre

def interMediateNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
fastNode = head
slowNode = head
while fastNode and fastNode.next.next:
fastNode = fastNode.next.next
slowNode = slowNode.next
return slowNode

image-20251002152125506