给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
自己原始解法： 显得十分的冗余啰嗦
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
quotient = 0
first = True
l3 = ListNode(0)
last_node = l3
while (l1 != None) and (l2 != None) :
new_node = ListNode(0)
new_node.val = (l1.val + l2.val + quotient) % 10
quotient = (l1.val + l2.val + quotient) // 10
if first:
last_node.val = new_node.val
first = False
else:
last_node.next = new_node
last_node = new_node
l1 = l1.next
l2 = l2.next
if l1 != None:
new_node = ListNode(0)
new_node.val = (l1.val + quotient) % 10
quotient = (l1.val + quotient) // 10
if first:
last_node.val = new_node.val
first = False
else:
last_node.next = new_node
last_node = new_node
while l1.next != None:
l1 = l1.next
new_node = ListNode(0)
new_node.val = (l1.val + quotient) % 10
quotient = (l1.val + quotient) // 10
last_node.next = new_node
last_node = new_node
if(quotient>0):
last_node.next=ListNode(1)
return l3
if l2 != None:
new_node = ListNode(0)
new_node.val = ( l2.val + quotient) % 10
quotient = (l2.val + quotient) // 10
if first:
last_node.val = new_node.val
first = False
else:
last_node.next = new_node
last_node = new_node
while l2.next != None:
l2 = l2.next
new_node = ListNode(0)
new_node.val = (l2.val + quotient) % 10
quotient = (l2.val + quotient) // 10
last_node.next = new_node
last_node = new_node
if(quotient>0):
last_node.next=ListNode(1)
return l3
if(quotient>0):
last_node.next=ListNode(1)
return l3
改进之后的解法：
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
dummyHead = ListNode(0)
cur_node = dummyHead
while (l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
sum = x + y + carry
carry = sum//10
cur_node.next = ListNode(sum%10)
cur_node = cur_node.next
if (l1 != None) :
l1 = l1.next
if (l2 != None) :
l2 = l2.next
if carry > 0:
cur_node.next = ListNode(1)
return dummyHead.next
字符串加法 链表加法都可以使用这种模板
class Solution {
public String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int carry = 0, i = num1.length()-1, j = num2.length()-1;
while(i >= 0 || j >= 0 || carry != 0){
if(i>=0) carry += num1.charAt(i--)-'0';
if(j>=0) carry += num2.charAt(j--)-'0';
sb.append(carry%10);
carry /= 10;
}
return sb.reverse().toString();
}
}
几个重要的改进：
1. 增加哨兵节点（哑结点），即首节点之前的节点，从而将后续节点一视同仁，不需要再考虑首节点的特殊性（例如我增加了flag标志区分）
2. 新建链表还是需要3个指针，哨兵指针（简化程序 且固定不动可以方便返回首节点） 当前指针（同时也是上一个指针 串起来整个链表） 新节点（每次新建的节点） cur_node.next = new_node ; cur_node = new_node
3. 在合并时的简化操作 我一开始的思路是如同合并链表 while and 两个链表不为空 再分析剩下的 后续的简化是 直接 用or 有一个不为空 则可以继续计算 （可以看到自己最初代码中有大量的重复工作） 只需把结束的节点置0
4. 注意考虑最后的进位（最高位进位） 循环结束的carry 进位最多只能是1
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
两种思路：
- 首先遍历找到链表长度，然后移动指针到要删除的前一位， 再就是 tmp.next = tmp.next.next 两次遍历链表
- 双指针法 （快慢指针法）两个指针一开始就保持一定的距离，当后一个指针到达末尾时，前一个指针就是要删除的位置的前一个 即保持相同距离 同时移动
- 两种方法中都可以用到 链表首部的哑结点（哨兵节点）-----------有链表的题要注意这种方法 可以不用考虑首节点的特殊性
- 注意一下判断条件 ！= None？ 其实如何判断都一样 自己捋清楚就好
第一种方法：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
tmp = ListNode(0)
tmp = head
length = 1
while tmp.next != None:
length += 1
tmp = tmp.next
#print(length)
#删除第一个节点?
if n == length:
head = head.next
return head
tmp = head
#移动指针到要删除元素的前一位
for i in range(1, length-n):
tmp = tmp.next
tmp.next = tmp.next.next
#remove_node = ListNode(0)
#remove_node = tmp.next
#tmp.next = remove_node.next
return head
2 快慢指针法
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 最简洁的方法 利用dummy的特殊 屏蔽掉首节点的特殊情况 此时移动
dummy = ListNode(0)
dummy.next = head
first = dummy
second = dummy
#second = dummy.next
for i in range(n):
first = first.next
# 上述移动到first和second 相隔n的位置
print(first.val)
while first.next != None:
second = second.next
first = first.next
second.next = second.next.next
return dummy.next
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
如同注释中介绍的 循环链表 找到起始位置 n-k%n 然后截取n的长度
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
#初步想法 拼接成两个长度的链表 然后k求余数 n-余数的下标 调整哑结点 如何复制一份链表 增加链表的长度
if head== None:
return
n = 1
dummyHead = ListNode(0)
dummyHead.next = head
while head.next:
n += 1
head =head.next
#print(n)
head.next = dummyHead.next
yushu = k % n
if yushu == 0:
head.next = None
return dummyHead.next
start = n - yushu
test = dummyHead.next
count = 0
while count < start:
test = test.next
count += 1
count_num = 1
real_head = test
while count_num < n:
test = test.next
count_num += 1
test.next = None
return real_head
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
# 自己一开始的做法 双指针法 一个cur指针 遍历整个数组 head指针作为结果指针(pre指针 ) 当cur.val == head.val and cur.next 终止 去判断是什么情况导致
# 可以做出来 但是对边界条件的判断比较慢 需要改进
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head
if not head :
return
if not head.next:
return head
#初始化一些指针
cur = head.next
#last = head
while cur:
while cur.val == head.val and cur.next:
cur = cur.next
#last = last.next
if cur.val == head.val:
#出现了cur达到终点
head.next = None
else:
head.next = cur
head = head.next
#last = head
cur = cur.next
return dummyHead.next
题解十分巧妙，直接的方法
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head
while head and head.next:
#十分的巧妙 在重复元素出现的时候 直接跳过 并且不修改head指针 ，
#即有重复就在不断地跳过重复元素 h.next = h.next.next 知道遇到不相等元素 才调整head指针的位置
# 最后一个元素同理 重复的最后next置为None 符合题意
if head.val == head.next.val:
head.next = head.next.next
else:
head= head.next
return dummyHead.next
递归解法 递归套路解决链表问题：
找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
#返回条件 只有一个元素时要返回
if not head or not head.next:
return head
#每一层干什么 返回什么
head.next = self.deleteDuplicates(head.next)
if head.val == head.next.val:
head = head.next
return head
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5 输出: 1->2->5
自己一开始的解法 注释比较详细
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head
if not head or not head.next:
return head
# 设置哑结点 从而第一个元素可以相同处理 last指向 哑结点 cur指向第一个
cur = head
last = dummyHead
while cur and cur.next:
# 出现了重复元素
if cur.val == cur.next.val:
# while循环来解决多个数重复的问题
while cur.next and cur.val == cur.next.val:
cur = cur.next
# 因为是最后一个元素（重复元素）而 跳出循环之后 直接舍弃最后的元素 置为none
if not cur.next:
last.next = None
# 某个数的重复处理完毕 进行下一个数 设置cur和last cur指向新的元素 last下一个元素为cur 即跳过了重复元素 再利用外层循环判断
# cur.val != cur.next.val:
else:
cur = cur.next
last.next = cur
# 普通两个不相等元素 直接往前进一步
else:
last = last.next
cur = cur.next
return dummyHead.next
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
一开始的想法：找出小于x的元素，存起来 并删除原链表中的元素 再次遍历 找到大于的元素 开始全部插入
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
#边界条件的处理
if not head or not head.next:
return head
dummyHead = ListNode(0)
dummyHead.next = head
flag = False
res = []
while head:
if head.val < x:
if flag:
#在大数之后出现的小数
res.append(head.val)
if head.next:
last.next = head.next
head = head.next
continue
else:
#print(last.val)
last.next = None
elif head.val >= x:
flag = True
head = head.next
last = last.next
#print(res)
#初步处理完 再遍历一次 然后插入链表
head = dummyHead.next
last = dummyHead
while head:
if head.val >= x:
#找到了当前应该插入位置的下一个 在last之后 head之前插入几个元素
for num in res:
tmp = ListNode(num)
tmp.next = last.next
last.next = tmp
last = last.next
break
head = head.next
last = last.next
return dummyHead.next
尝试上述两个步骤在一次遍历中来完成 可以实现
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现思路 ：以1->2->3->4->5, m = 2, n=4 为例:
定位到要反转部分的头节点 2，head = 2；前驱结点 1，pre = 1；
当前节点的下一个节点3调整为前驱节点的下一个节点 1->3->2->4->5,
当前结点仍为2， 前驱结点依然是1，重复上一步操作。。。
1->4->3->2->5.
注意在交换链表位置的时候 注意指针的顺序 （本题目中是后到前的顺序） 注意是如何翻转的 是依次交换相邻的两个元素 无法直接交换首尾元素 只能交换相邻元素的
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
dummyHead = ListNode(0)
dummyHead.next = head
last = dummyHead
for i in range(m-1):
last = last.next
head = last.next
# 注意内部 在使用一项之后立即修改 有一定的顺序 注意观察 插入时往往是先保存后面的next 再插入
# 一次for循环之后 head往后移了一位 last不变 仍然是翻转的节点之前
for i in range(n-m):
t = head.next
head.next = t.next
t.next = last.next
last.next = t
return dummyHead.next
class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return new_next, new_random = None, None if head.next: new_next = self.copyRandomList(head.next) if head.random: if head.next: if head.random.val != head.next.val: #是本身的情况 if head.random.val == head.val: new_random = head new_random = self.copyRandomList(head.random) else: new_random = new_next else: if head.random.val == head.val: new_random = head else: new_random = self.copyRandomList(head.random)
new_head = Node(head.val, new_next, new_random)
return new_head
判断一个链表是否有环
哈希表的方法：
class Solution(object):
def hasCycle(self, head):
#尝试使用题解的两种方法-1 哈希表法 即保存下来再判断
hash_set = set()
while head:
if head in hash_set:
return True
hash_set.add(head)
head = head.next
return False
快慢指针的方法： 若有环最终快指针能遇到慢指针 否则不会
class Solution(object):
def hasCycle(self, head):
#尝试使用题解的两种方法-2 快慢指针法 快指针每次走2步 慢指针每次走1步
fast = head
slow = head
first = True
while fast and fast.next:
if fast == slow:
if first:
first = False
else:
return True
fast = fast.next.next
slow = slow.next
return False
给定一个链表，返回链表开始入环的第一个节点 如果链表无环，则返回 null。
方法一直接在141的基础上返回相同的节点即可
方法二快慢指针的方法： 若有环最终快指针能遇到慢指针,再走一定的步数 必定相遇在开始节点 2 （F+a） = F + a + n(a+b) -> f = b+ (n-1)(a+b) 则从head再运行f步 会相遇 见题解 https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode/
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
#return True
if not fast or not fast.next:
return None
cur = head
while cur != slow:
cur = cur.next
slow = slow.next
return slow
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
自己觉得困难的主要是无法倒序查找节点 即没有反向的指针来往回走--------------------》》》将链表反转 如何反转链表 在本题中综合了找中点（双指针） 翻转链表（92题） 拼接链表 也可以拆分成两个链表 然后再合并操作
class Solution:
def reorderList(self, head: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
#分为3个步骤 找中点 翻转后半部分 拼接链表
#找中点 可以使用双指针法
if not head:
return
if not head.next:
return
dummy = ListNode(0)
dummy.next = head
last = dummy
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
last = last.next
#print(last.val, slow.val)
#翻转后半部分
while slow.next:
t = slow.next
slow.next = t.next
t.next = last.next
last.next = t
#print(dummy.next)
#拼接两部分链表
mid = last.next
head = dummy.next
#下面这个判断条件是自己在尝试过 奇偶数的不同情况之后 得到的 就是mid-》last代表前面的已经处理好
while head != last :
t = mid.next
last.next = t
mid.next = head.next
head.next = mid
head = head.next.next
mid = last.next
#print(dummy.next)
#print(last.val, mid.val)
自己使用的是递归的方式 ，即将一个新的元素插入到已经拍好序的链表中
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head:
return
if not head.next:
return head
#直觉上可以使用递归的方式 不过现在的是逆序的插入排序
res = head
tmp = self.insertionSortList(head.next)
if res.val <= tmp.val:
res.next = tmp
return res
else:
tmp_head = tmp
tmp_next = tmp.next
while tmp_next:
if tmp_next.val > res.val:
tmp_head.next = res
res.next = tmp_next
return tmp
tmp_next = tmp_next.next
tmp_head = tmp_head.next
tmp_head.next = res
res.next = None
return tmp
查看评论区的方法： pre= dummy 用来每次内部比较循环 head用来指向当前已排序的最后一个位置 head.next 是要排序的元素 很重要的剪枝是： head.next 先和排好序的上一位进行比较 如果大于则不需要排序，直接下一位 否则进入 pre指向的内层循环来比较 先循环找到应该插入的位置 然后插入
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head:
return
if not head.next:
return head
dummy = ListNode(0)
dummy.next = head
pre = dummy
while head and head.next:
if head.val < head.next.val:
head = head.next
continue
pre = dummy
while pre.next.val < head.next.val:
pre = pre.next
#出现了 要插入的位置 即在pre之后 在pre.next 之前
cur = head.next
# 原来写的出现了问题 head = head.next.next 现在只是重新串联了起来 并没有直接移动head指针
head.next = cur.next
cur.next = pre.next
pre.next = cur
return dummy.next
查看题解一种更加清晰的方式， 和上一个方法的没有太大区别 只是实现起来简单容易理解 用了一个新的链表 上述解法2 是在原来的基础上直接进行修改 没有想上一题解那样 可以直接 和上一个元素比较 来剪枝操作 减少 （改进看https://leetcode-cn.com/problems/insertion-sort-list/solution/jia-ge-tailsu-du-jiu-kuai-liao-by-powcai/）
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
pre = dummy
# dummy.next = head 这个类似于重新构造一个链表 所以不需要连接head指针 注意 往dummy指向的新链表序列不断地插入元素
cur = head
while cur:
#保存下一个节点的位置
temp = cur.next
#找到插入位置
while pre.next and pre.next.val < cur.val:
pre = pre.next
#找到了应该插入的位置 cur 插入pre之后
cur.next = pre.next
pre.next = cur
cur = temp
pre = dummy
return dummy.next
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 主要是时间复杂度的限制 在链表的情况下完成nlogn的时间复杂度
在这个时间复杂度的提醒下 可以想到归并排序 本题用到的是 自底向上的归并排序 不断合并相邻的元素 不断扩大 自底向上没有用到栈 符合O(1)的空间复杂度要求
具体可以查看 https://leetcode-cn.com/problems/sort-list/solution/148-pai-xu-lian-biao-bottom-to-up-o1-kong-jian-by-/
注意一下 主要的两种函数 merge（很常规 需要记住） 和cut(依据长度切分链表 返回后部的头结点)
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
length = 0
while head:
length += 1
head = head.next
size = 1
while size < length:
cur = dummy.next
tail = dummy
while cur:
left = cur
right = self.cut(left, size)
cur = self.cut(right, size)
#在cut之后 原链表是断的 需要由tail指针连接起来 在一次while cur 循环中 按照当前size值 不断切分 然后合并 移动tail指向最后
# 例如 先按照1划分 合并之后 相邻2位有序 下次按照2划分（这两个刚好有序） 再合并为4
tail.next = self.merge(left, right)
while tail.next:
tail = tail.next
size *= 2
return dummy.next
#插入排序会出现超时问题 不符合题意中的时间复杂度要求 需要对排序算法时间重新整理总结
#cut(l, n)函数 一种spilt操作 主要用来断链 切分链表 将链表l切除前n个节点，返回后半部分的链表头
def cut(self, l, n):
count = 0
while l:
count += 1
if count == n:
#注意不能只切分 返回后面的指针 还要将前半部分的指针置空
res = l.next
l.next = None
return res
l = l.next
#n数量比l的长度长 返回空
return None
#非常常见的合并链表的算法 将两个链表合并在一起 有序合并 返回合并后的首节点
def merge(self, l1, l2):
dummy = ListNode(-1)
pre = dummy
while l1 and l2:
if l1.val <= l2.val:
pre.next = l1
pre = l1
l1 = l1.next
else:
pre.next = l2
pre = l2
l2 = l2.next
if l1:
pre.next = l1
if l2:
pre.next = l2
return dummy.next
同时也可以直接考虑归并排序 上到下的
# 上到下的排序
l = mergesort(head)
r = mergesort(head)
merge(l, r)
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# 在京东面试遇到过的原题
# 让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置
# 所以关键就是要消除两个链表的长度差 长链表先走，消除长度差，尾部就能对齐 然后一起找到
# 拼接链表 在于 如果没有相交点 二者会在null相遇
# 如果用.next会一直死循环（如果不相交）。不用next，最后不相交的话会都等于None而结束循环
if not headA or not headB:
return None
ha, hb = headA, headB
while ha!= hb:
ha = ha.next if ha else headB
hb = hb.next if hb else headA
return ha