链表的反转-leetcode_反转链表 leetcode

LeetCode- 206 反转链表

思路1：迭代反转
可以使用虚拟头节点来进行头插法
思路2：递归反转（一次拆掉一个节点并递归处理剩余的子链表）
解题重点：
一定要有三个指针，一个放反转前，一个放翻转后，一个放反转时

class Solution: 
	def reverseList(self, head: ListNode) -> ListNode: 
		pre = None 
		cur = head 
		while (cur): 
			tem = cur.next 
			cur.next = pre 
			pre = cur 
			cur = tem 
		return pre

1
2
3
4
5
6
7
8
9
10
11

LeetCode 92 反转链表II

使用虚拟头结点（dummy head）
通常用于链表的首地址有可能改变的情况
解题重点：
1.与上一题反转链表函数无大差异，但是需要改变反转停止条件，此时为反转K个链表
2.主体函数找到起始反转位置即可，剩下的交给反转函数
3.找到起始反转位置的前一个结点，方便反转后链接

class Solution: 
	def reverse(self,head,k):#反转k个链表 
		pre = None 
		cur = head 
		for _ in range(k): 
			tem = cur.next 
			cur.next = pre 
			pre = cur 
			cur = tem 
		head.next = cur 
		return pre 
		
	def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: 
	empty = ListNode() 
	empty.next = head 
	p = empty 
	for _ in range(left - 1): 
		p = p.next 
	p.next = self.reverse(p.next,right - left + 1) 
	return empty.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

LeetCode 25 K个一组翻转链表

思路：先判断是否有K个元素 然后对这K个节点进行反转 最后拆装一下首尾部分
解题重点：
1.保证反转函数正确，反转函数需要判断传入的链表是否满足k个结点
2.主体函数通过找到起始反转位置，同时判断下一个位置够不够k个（题目要求剩余的结点不足k
个则保留
3.一定需要将复杂问题拆分解决，先解决反转函数，然后反转函数升级改造为要判断K个结点

class Solution: 
	def reverse(self,head,k):#反转K个结点（这个函数的链表输入不一定是有k个链表的） 
			pre = head#pre = None 
			cur = head 
			cnt = 0
			while (pre and cnt < k - 1):#传入的需要被反转的链表是否够k个 
				pre = pre.next 
				cnt += 1 
			if pre == None:return head 
			pre = None#出bug的时候:这儿是没有的 
			for _ in range(k): 
				tem = cur.next 
				cur.next = pre 
				pre = cur 
				cur = tem 
			head.next = cur 
			return pre
	
	def reverseKGroup(self, head: ListNode, k: int) -> ListNode: 
		empty = ListNode() 
		empty.next = head 
		pre = empty 
		while (1): 
			pre.next = self.reverse(pre.next,k) 
			cnt = 0 
			while pre and cnt < k:#判断接下来的链表结点够不够k个 
				cnt += 1 
				pre = pre.next 
			if pre == None:
				break 
		return empty.next
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

LeetCode 61 旋转链表

思路：把整个链表首尾相接 向后走K位后将环拆开
解题重点：
1.将问题转化为环形链表重新剪开环（贪吃蛇现象）
2.如何将链表成环，成环操作
3.将右边第K个结点旋转，转化为从头部到第len-k个位置，但是剪开环的时候需要他的前一个位
置才能操作
4.需要得到新的链表头的地址，然后再操作剪环

class Solution: 
	def rotateRight(self, head: ListNode, k: int) -> ListNode: 
		if not head or not head.next: return head 
		pre = head 
		length = 1 
		while pre.next: 
			pre = pre.next 
			length += 1 
		k = k % length 
		pre.next = head#链表成环了 
		for _ in range(length - k - 1):#保证拿到第len-k的结点的地址， 
			head = head.next 
		new_head = head.next #保证newhead地址，我们先拿到手 
		head.next = None#断开结点 
		return new_head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode #24 两两交换链表中的节点

思路与LeetCode #25完全一致，是K = 2的简单情形。
解题重点：
1.K个链表反转的特例，将K=2即可
2.直接两两反转也是很简单的，保证反转时有三个指针标记地址即可，切记画图!!!\

class Solution: 
	def swapPairs(self, head: ListNode) -> ListNode: 
		if not head:return None 
		empty = ListNode() 
		empty.next = head 
		T = empty 
		while T.next and T.next.next: 
			node1 = T.next 
			node2 = T.next.next 
			T.next = node2 
			node1.next = node2.next 
			node2.next = node1 
			T = node1 
		return empty.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14