不做大哥好多年
xiaonaiqiang
2021-06-19
目录

21.链表

# ① 双指针

# 01.两数相加

  • 2.两数相加 (opens new window)

  • 给你两个 非空 的链表，表示两个非负的整数

  • 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字

  • 请你将两个数相加，并以相同形式返回一个表示和的链表

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807
1
2
3

1、Python

  • 1.先将l1和l2头节点的值加起来赋值给新链表的头节点
  • 2.遍历两个链表，只要有一个链表还没有遍历到末尾，就继续遍历
  • 3.每次遍历生成一个当前节点cur的下一个节点，其值为两链表对应节点的和再加上当前节点cur产生的进位
  • 4.更新进位后的当前节点cur的值
  • 5.循环结束后，因为首位可能产生进位，因此如果cur.val是两位数的话，新增一个节点
  • 6.返回头节点
class ListNode(object):
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next


def addTwoNumbers(l1, l2):
    head = ListNode(l1.val + l2.val)          # 赋值给新链表的头节点
    cur = head                                # 新链表头部
    while l1.next or l2.next:                 # 只要有一个链表还没有遍历到末尾，就继续遍历
        l1 = l1.next if l1.next else ListNode(0)    #指针移动 到达末尾val默认为0
        l2 = l2.next if l2.next else ListNode(0)
        cur.next = ListNode(l1.val + l2.val + cur.val // 10)   # 相加结果赋值给新链表
        cur.val = cur.val % 10               # 以前存入节点值可能会大于10，取余更新

        cur = cur.next                       # 指针指向新链表的下一个节点
        
    # 遍历到最后一个节点时如果大于10，在进行一次进一操作
    if cur.val >= 10:
        cur.next = ListNode(cur.val // 10)   # 新建一个节点存放进一的位
        cur.val = cur.val % 10               # 将大于10的节点进行趋于后重新赋值
    return head

if __name__ == "__main__":
    l1 = ListNode(1, ListNode(3, ListNode(3)))    # 133
    l2 = ListNode(1, ListNode(2))                 # 12
    l = addTwoNumbers(l1, l2)
    print(l.val)                # 2
    print(l.next.val)           # 5
    print(l.next.next.val)      # 3
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

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	head := &ListNode{Val: l1.Val+l2.Val}  // 赋值给新链表的头节点
	cur := head  // 新链表头部
	// 只要有一个链表还没有遍历到末尾，就继续遍历
	for l1.Next != nil || l2.Next != nil {
		// 指针向下移动一位，如果链表已经遍历完那么就添加一个val为0的节点
		if l1.Next != nil {
			l1 = l1.Next
		}else {
			l1 = &ListNode{Val: 0}
		}
		if l2.Next != nil {
			l2 = l2.Next
		}else {
			l2 = &ListNode{Val: 0}
		}
		// 在新链表添加一个元素，值为 两个链表节点的值 + 进位的值
		cur.Next = &ListNode{Val: l1.Val + l2.Val + cur.Val / 10}
		cur.Val = cur.Val % 10  // 因为以前存入的节点值可能会大于10，所以对存入的值进行更新，区域即可
		cur = cur.Next          // 指针指向新链表的下一个节点
	}
	// 遍历到最后一个节点时如果大于10，在进行一次进一操作
	if cur.Val >= 10 {
		cur.Next = &ListNode{Val: cur.Val / 10}  // 新建一个节点存放进一的位
		cur.Val = cur.Val % 10                   // 将大于10的节点进行趋于后重新赋值
	}
	return head
}

func main() {
	l1 := &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: &ListNode{Val: 3, Next: nil}}}
	l2 := &ListNode{Val: 5, Next: &ListNode{Val: 6, Next: &ListNode{Val: 4, Next: nil}}}

	l := addTwoNumbers(l1, l2)
	for l != nil {
		fmt.Print(l.Val, "\t")
		l = l.Next  // 7       0       8
	}
}
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
41
42
43
44

# 02.相交链表起点

1、Python

  • 同时遍历headA, headB，当到达末尾时，把另一个的头指针拼接到后面
  • 这样就会形成一个环，相交点就是两个单链表相交的起始节点
  • headA走的路径：4-》1-》8-》4-》 5-》0-》1-》8
  • headB走的路径：5-》0-》1-》8-》4-》 4-》1-》8
class ListNode:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

def getNode(headA, headB):
    p1 = headA
    p2 = headB
    while p1 != p2:
        p1 = headB if p1 is None else p1.next    # 如果p1链表到达末尾，p1=headB 继续遍历
        p2 = headA if p2 is None else p2.next    # 如果p2链表到达末尾，p2=headA 继续遍历
    return p1

if __name__ == '__main__':
    headA, n2, n3, n4 = ListNode(4), ListNode(1), ListNode(8), ListNode(4)
    headA.next = n2
    n2.next = n3
    n3.next = n4
    headB,n6,n7  = ListNode(5), ListNode(0), ListNode(1)
    headB.next = n6
    n6.next = n7
    n7.next = n3
    print( getNode(headA, headB).val )  # 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
	p1 := headA
	p2 := headB
	for p1 != p2 {
		if p1 != nil {
			p1 = p1.Next
		}else {
			p1 = headB  // 如果p1链表到达末尾，p1=headB 继续遍历
		}
        
		if p2 != nil {
			p2 = p2.Next
		}else {
			p2 = headA  // 如果p2链表到达末尾，p2=headA 继续遍历
		}
	}
	return p1
}

func main() {
	headA := ListNode{Val: 4}
	n2 := ListNode{Val: 1}
	n3 := ListNode{Val: 8}
	n4 := ListNode{Val: 4}
	headA.Next = &n2
	n2.Next = &n3
	n3.Next = &n4

	headB := ListNode{Val: 5}
	n6 := ListNode{Val: 0}
	n7 := ListNode{Val: 1}
	headB.Next = &n6
	n6.Next = &n7
	n7.Next = &n3

	l := getIntersectionNode(&headA, &headB)
	fmt.Println(l.Val)  // 8
}
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
41
42
43

# 03.环形链表

1、Python

  • 快慢指针解决
  • 慢指针每次走一步，快指针每次走两步
  • 只要成环肯定快指针会和慢指针重合
class ListNode:
    def __init__(self,val=None,next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    if not head or not head.next:
        return False
    slow = head             # 慢指针每次走一步
    fast = head.next        # 快指针每次走两步
    while slow != fast:
        if not fast or not fast.next:  # 如果快指针遍历结束，证明不成环
            return False
        slow = slow.next
        fast = fast.next.next
    return True

if __name__ == '__main__':
    p1, p2, p3, p4  = ListNode(1),ListNode(2), ListNode(0),  ListNode(-4)
    p1.next = p2
    p2.next = p3
    p3.next = p4
    p4.next = p2
    print( hasCycle(p1) )  # True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow := head       //  慢指针每次走一步
	fast := head.Next    // 快指针每次走两步
	for slow != fast {
		if fast == nil || fast.Next == nil {  //  如果快指针遍历结束，证明不成环
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true  // 快慢指针相遇就跳出循环，返回True，证明成环
}

func main() {
	head := ListNode{Val: 1}
	p2 := ListNode{Val: 2}
	p3 := ListNode{Val: 0}
	p4 := ListNode{Val: -4}
	head.Next = &p2
	p2.Next = &p3
	p3.Next = &p4
	p4.Next = &p2

	l := hasCycle(&head)
	fmt.Println(l)  // true
}
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

# 04.环形链表II

  • 142.环形链表II (opens new window)

  • 给定一个链表的头节点 head ，返回链表开始入环的第一个节点，如果链表无环，则返回 null

  • 找到链表中环的起始节点，如果链表中没有环，则返回 null

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点
1
2
3

1、Python

  • 依然可以使用快慢指针首先让快慢指针相遇，确认链表中存在环
  • 然后将其中一个指针移动到链表头节点，两者以相同的速度移动，再次相遇时所在的节点就是环的起始节点
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def detectCycle(head):
    if not head or not head.next:
        return None
    
    slow, fast = head, head
    
    # 首先判断链表中是否有环
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
    
    # 找到环的起始节点
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow
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

# 05.链表中倒数第k个节点

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
1
2

1、Python

  • 倒数第K个节点 (opens new window)

  • 这道题采用快慢指针的方式，定义一个计数器

  • fast指针先开始移动，当fast指针走到第k个时slow指针开始走

  • 这样当fast指针到达链表末尾，slow指针正好指向 倒数第k个点

class ListNode:
   def __init__(self,val=None,next=None):
       self.val = val
       self.next = next

def getKthFromEnd(head, k):
   slow = fast = head
   n = 0
   while fast:
       # fast指针先开始移动，当计数器走过K个数后，slow指针在开始移动
       if n>=k:
           slow = slow.next
       fast = fast.next
       n += 1
   return slow


if __name__ == '__main__':
   root = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
   print( getKthFromEnd(root, 2).val )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 06.训练计划II

输入：head = [2,4,7,8], cnt = 1
输出：8
1
2

1、Python

  • 初始化两个指针 fast 和 slow，都指向链表的头节点 head

  • 让 fast 指针先向前移动 cnt 步，这样 fast 指针和 slow 指针之间的距离就为 cnt

  • 然后同时移动 fast 和 slow 指针，直到 fast 指针到达链表末尾

  • 此时，slow 指针指向的节点就是倒数第 cnt 个节点

class Solution:
    def trainingPlan(self, head, k):
        slow = fast = head
        n = 0
        while fast:
            # fast指针先开始移动，当计数器走过K个数后，slow指针在开始移动
            if n>=k:
                slow = slow.next
            fast = fast.next
            n += 1
        return slow
1
2
3
4
5
6
7
8
9
10
11

# 07.删除链表的倒数第N个结点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
1
2

1、Python

  • 使用两个指针，第一个指针先走 n 步，然后两个指针一起移动，直到第一个指针到达链表的末尾
  • 此时，第二个指针的位置正好在倒数第 n 个节点的前一个节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def removeNthFromEnd(self, head, n):
        new_head = ListNode(0, head)     # 创建一个虚拟头节点，以处理删除头节点的情况
        fast = new_head
        slow = new_head

        for _ in range(n + 1):           # 将 fast 指针向前移动 n + 1 步
            fast = fast.next

        # 移动 fast 和 slow 指针直到 fast 到达链表的末尾
        while fast is not None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next        # 删除倒数第 n 个节点
        return new_head.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  • 2）删除中间节点(简单)

    • 面试题 02.03.删除中间节点 (opens new window)

      • 实现一种算法，删除单向链表中间的某个节点（即不是第一个或最后一个节点）

      • 假定你只能访问该节点

    • 输入：单向链表a->b->c->d->e->f中的节点c
结果：不返回任何数据，但该链表变为a->b->d->e->f
      1
      2

class Solution:
    def deleteNode(self, node):
        node.val = node.next.val          # 复制 node.next 到 node
        node.next = node.next.next        # 从链表中删除 node.next
1
2
3
4

# 08.删除排序链表中的重复元

1、Python

class Solution:
    def deleteDuplicates(self, head):
        if not head:
            return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:    # 如果当前节点值与下一个节点值相同
                cur.next = cur.next.next   # 跳过下一个节点，删除重复节点
            else:
                cur = cur.next             # 否则，继续移动到下一个节点
        return head
1
2
3
4
5
6
7
8
9
10
11

# 09.删除排序链表中的重复元素II

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
1
2

1、Python

  • 如果当前节点与下一个节点重复，跳过所有重复节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def deleteDuplicates(head):
    new_head = ListNode(0)
    new_head.next = head
    cur = new_head                # 使用cur指针指向新链表

    while head:
        # 如果当前节点与下一个节点重复，跳过所有重复节点
        if head.next and head.val == head.next.val:
            while head.next and head.val == head.next.val:
                head = head.next
            cur.next = head.next  # 跳过所有重复元素，指向下一个不重复的元素
        else:
            cur = cur.next        # 如果不重复，移动 cur 指针
        head = head.next          # 继续移动 head 指针

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

# ② 反转

# 11.反转链表

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
1
2

1、Python

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head):
        if head == None:
            return None
        l, r, cur = None, None, head        # 左指针、右指针、游标
        while cur.next != None:
            l = r                   # 左侧指针指向以前右侧指针位置
            r = cur                 # 右侧指针前进一位指向当前游标位置
            cur = cur.next          # 游标每次向前进一位
            r.next = l              # 右侧指针指向左侧实现反转
        cur.next = r                # 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
        return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	cur := head         // 游标
	var L, R  *ListNode   // 左指针、右指针
	for cur.Next != nil {
		L = R           // 左侧指针指向以前右侧指针位置
		R = cur          // 右侧指针前进一位指向当前游标位置
		cur = cur.Next     // 游标每次向前进一位
		R.Next = L        // 右侧指针指向左侧实现反转
	}
	cur.Next = R  // 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
	return cur
}

func main() {
	l := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: nil}}}
	l1 := reverseList(l)
	for l1 != nil {
		fmt.Print(l1.Val, "\t")   // 3       2       1
		l1 = l1.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

# 12.反转链表 II

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
1
2

1、Python

  • 使用反转链表的解法，反转 left 到 right 部分以后，再拼接起来
  • 我们还需要记录 left 的前一个节点，和 right 的后一个节点
  • 第 1 步：先将待反转的区域反转；
  • 第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseBetween(self, head, l, right):
        newhead = ListNode(0)             # 新建一个链表
        newhead.next = head               # 将新链表插入到以前链表的头部

        cnt = 0
        stack = []
        cur = newhead                     # 使用一个指针指向新链表头部

        while cnt < l:                    # 只要指针 还没有到左侧分割位置就移动指针
            cnt += 1
            tmp1 = cur                    # 保存m-1节点（l的前一个节点）
            cur = cur.next

        while cnt <= right:               # 只要指针还没有到达right位置 就继续循环
            stack.append(cur)
            cnt += 1
            cur = cur.next
        tmp2 = cur                        # 保存n+1节点（right的后一个节点）

        while stack != []:                # 只要栈不为空就继续弹出元素
            tmp1.next = stack.pop()       # 将栈中的元素依次弹出并添加到 l的后面
            tmp1 = tmp1.next

        tmp1.next = tmp2              # 栈为空时，证明要反转的数据反转完成，再把right后面部分数据拼接到链表

        return newhead.next           # 返回新链表的下一个位置，就是原有链表的头部

if __name__ == "__main__":
    # 1-->  2-->3-->4  -->5
    lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
    l = Solution().reverseBetween(lst, 2, 4)
    while l:
        print(l.val)  # 1-->  4-->3-->2  -->5
        l = l.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
32
33
34
35
36
37
38
39
40

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	newHead := &ListNode{Val: 0}   // 新建一个链表
	newHead.Next = head            // 将新链表插入到以前链表的头部
	count := 0
	theStack := []*ListNode{}
	cur := newHead                 // 使用一个指针指向新链表头部
	var temp1, temp2 *ListNode
	for count < left {             // 只要指针 还没有到左侧分割位置就移动指针
		count += 1                 // 数量加一，以便保持count和cur指针一起移动
		temp1 = cur                // 保存m-1节点（left的前一个节点）
		cur = cur.Next             // 指针向下移动一位
	}
	for count <= right {           // 只要指针还没有到达right位置 就继续循环
		theStack = append(theStack, cur)   // 将需要反转的节点加入到栈中
		count += 1                 // count数量加一保持和指针移动一致
		cur = cur.Next             // 指针向右移动一位
	}
	temp2 = cur                    // 保存n+1节点（right的后一个节点）
	fmt.Println(theStack, theStack != nil)
	for len(theStack) != 0 {       // 只要栈不为空就继续弹出元素
		temp1.Next = theStack[len(theStack) - 1]    // 将栈中的元素依次弹出并添加到 left的后面
		theStack = theStack[:len(theStack)-1]
		temp1 = temp1.Next
	}
	temp1.Next = temp2   // 栈为空时，证明要反转的数据反转完成，再把right后面部分数据拼接到链表
	return newHead.Next  // 返回新链表的下一个位置，就是原有链表的头部
}

func main() {
	//  1-->  2-->3-->4  -->5
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}}}}
	l := reverseBetween(head, 2,4)

	// 1       4       3       2       5
	for l != nil {
		fmt.Print(l.Val, "\t")
		l = l.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
32
33
34
35
36
37
38
39
40
41
42
43
44

# 13.K 个一组翻转链

  • 25.K 个一组翻转链表 (opens new window)

  • 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表

  • k 是一个正整数，它的值小于或等于链表的长度如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序

1、Python

  • cur指针从链表head头开始进行遍历，每次满足cnt=k时

  • 调用reverseLinkedList方法对这部分链表反转并返回新链表的新head

  • 递归然后递归调用 reverseLinkedList，传入 cur现在的指针位置，重新计算即可

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseKGroup(self, head, k):
        def reverseLinkedList(head, k):     # 辅助函数：翻转链表
            prev, curr = None, head
            while k:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
                k -= 1
            return prev

        count = 0                   # 统计链表长度，检查是否有足够的节点进行翻转
        cur = head
        while cur and count < k:
            cur = cur.next
            count += 1

        if count == k:
            reversed_head = reverseLinkedList(head, k)  # 如果有 k 个节点，进行翻转
            head.next = self.reverseKGroup(cur, k)      # 递归处理下一部分并将其连接到当前翻转部分的末尾
            return reversed_head
        else:
            return head                 # 递归处理下一部分并将其连接到当前翻转部分的末尾


if __name__ == "__main__":
    # 辅助函数：打印链表
    def printList(node):
        while node:
            print(node.val, end=" -> " if node.next else "")
            node = node.next
        print()
    # 构建链表：1 -> 2 -> 3 -> 4 -> 5
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)

    # 调用函数并打印结果
    k = 2
    print("原链表:")
    printList(head)

    new_head = Solution().reverseKGroup(head, 2)
    print(f"每 {k} 个节点一组翻转后的链表:")
    printList(new_head)
# 原链表:
# 1 -> 2 -> 3 -> 4 -> 5
# 每 2 个节点一组翻转后的链表:
# 2 -> 1 -> 4 -> 3 -> 5
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# 14.回文链表

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true
1
2
3
4
5

1、Python - 使用快慢两个指针，快指针每次走两步，慢指针每次走一步 - 慢指针移动的时候同时定义L，R两个指针，将原始链表前半部分反转 - 当快指针走到链表尾部是，这个时候是这样的 - slow慢指针正好走到了原始链表中间位置 - R右指针正好将原始链表中间部分反转了

 - 此时只需要一一对比是否每一个值是否相等即可

class ListNode:
    def __init__(self,val=None,next=None):
        self.val = val
        self.next = next

def isHW(head):
    L, R, slow, fast = None, None, head, head
    while fast and fast.next:
        fast = fast.next.next

        # 反转链表
        R = slow           # 右指针向右走一步
        slow = slow.next   # 慢指针游标向右移动一位
        R.next = L         # 右指针的下一个节点指向左指针
        L = R              # 左指针向右移动一位

    if fast:               # 如果是偶数个，快指针还有一步没有走，所以需要再走一步
        slow = slow.next   # 最后slow就指向了链表中间位置

    # 这是slow指针指向链表中间位置，R指针指向的是原始链表前半部分的反转头部
    while slow and R:
        if slow.val != R.val:
            return False
        slow = slow.next
        R = R.next
    return True


if __name__ == '__main__':
    l = ListNode(1,ListNode(2,ListNode(2,ListNode(1))))
    print( isHW(l) )  # True
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

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func isPalindrome(head *ListNode) bool {
	slow := head
	fast := head
	var L, R  *ListNode
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next

		// 反转链表
		R = slow   // 右指针向右走一步
		slow = slow.Next  // 慢指针游标向右移动一位
		R.Next = L  // 右指针的下一个节点指向左指针
		L = R  // 左指针向右移动一位
	}
	// 如果是偶数个，快指针还有一步没有走，所以需要再走一步
	if fast != nil {
		slow = slow.Next  // 最后slow就指向了链表中间位置
	}
	// 这是slow指针指向链表中间位置，R指针指向的是原始链表前半部分的反转头部
	for slow != nil && R !=nil {
		if slow.Val != R.Val {
			return false
		}
		slow = slow.Next
		R = R.Next
	}
	return true
}

func main() {
	head := ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 2, Next: &ListNode{Val: 1}}}}

	l := isPalindrome(&head)
	fmt.Println(l)  // true
}
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

# 15.回文链表

输入：head = [1,2,2,1]
输出：true
1
2

1、Python

  • 快慢指针，快指针到达末尾时，慢指针正好到达链表中间位置
  • 以慢指针为起点对链表后半部分反转，反转后的链表头指针为 cur
  • 遍历反转后的链表，与原有链表值依次比较，判断是否时回文
class Solution:
    def isPalindrome(self, head):
        if not head or not head.next:
            return True            # 如果链表为空或只有一个节点，则它必定是回文

        # 使用快慢指针找到链表的中间节点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 反转链表的后半部分
        cur = None                # cur 指针指向反转后的链表头
        while slow:
            next_node = slow.next
            slow.next = cur
            cur = slow
            slow = next_node

        # 此时，cur 指针指向反转后的链表头，即链表的后半部分
        l, r = head, cur
        while r:                  # 只需要比较后半部分的长度即可
            if l.val != r.val:
                return False
            l = l.next
            r = r.next

        return True
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

# 16.两两交换链表中的节点

1、Python

  • 伪头节点：使用一个伪头节点 dummy 以简化对链表头节点的处理

  • 交换操作：

    • first 和 second 分别指向当前需要交换的两个节点

    • 将 prev.next 指向 second，即新的头节点

    • 更新 first.next 使其指向 second.next

    • 更新 second.next 使其指向 first，完成交换

  • 更新指针：

    • 将 prev 移动到 first（交换后的节点）

    • 将 head 移动到下一个待交换的节点（即 first.next）

  • 返回新头节点：伪头节点的下一个节点是新的头节点

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head):
        # 创建一个伪头节点，以便处理边界情况
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy  # prev是当前链表中前一个已交换的节点

        while head and head.next:
            # 获取要交换的两个节点
            first = head
            second = head.next

            # 进行交换
            prev.next = second
            first.next = second.next
            second.next = first

            # 移动到下一个需要交换的节点
            prev = first
            head = first.next

        return dummy.next  # 返回新的头节点

if __name__ == "__main__":
    lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))  # 1-->2-->3-->4
    l = Solution().swapPairs(lst)
    while l:
        print(l.val)  # 2 1 4 3
        l = l.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
32
33
34

# ③ 合并排序

# 21.合并两个有序链表

输入：l1 = 1->2->4, l2 = 1->3->4
输出：1->1->2->3->4->4
1
2

1、Python

  • 我们可以用迭代的方法来实现上述算法
  • 当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里
  • 当一个节点被添加到结果里之后，将对应链表中的节点向后移一位
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(self, l1, l2):
        head = ListNode(-1)               # head是新链表的头部
        cur = head                        # 我们维护一个cur 指针，我们需要做的是调整它的 next 指针
        while l1 and l2:                  # 我们重复以下过程，直到 l1 或者 l2 指向了 null
            if l1.val <= l2.val:     # 如果l1值小就将l1节点加到新链表后面
                cur.next = l1
                l1 = l1.next
            else:                    # 否则，我们对 l2 做同样的操作
                cur.next = l2
                l2 = l2.next
            cur = cur.next                 # 不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        cur.next = l1 if l1 is not None else l2
        return head.next


if __name__ == "__main__":
    l1 = ListNode(1, ListNode(2, ListNode(4)))  # 1->2->4
    l2 = ListNode(1, ListNode(3, ListNode(4)))  # 1->3->4
    l = Solution().mergeTwoLists(l1, l2)

    while l:
        print(l.val)  # 1 1 2 3 4 4
        l = l.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

2、Go

输入：l1 = 1->2->4, l2 = 1->3->4
输出：1->1->2->3->4->4
1
2
type ListNode struct {
	Val     int
	Next    *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	head := &ListNode{Val: -1}  // head是新链表的头部
	cur := head                 // 我们维护一个cur 指针，我们需要做的是调整它的 next 指针
	for list1 != nil && list2 != nil {   // 我们重复以下过程，直到 l1 或者 l2 指向了 null
		if list1.Val <= list2.Val {		 // 如果l1值小就将l1节点加到新链表后面
			cur.Next = list1
			list1 = list1.Next
		} else {                         // 否则，我们对 l2 做同样的操作
			cur.Next = list2
			list2 = list2.Next
		}
		cur = cur.Next           // 不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位
	}
	// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
	if list1 != nil {
		cur.Next = list1
	}
	if list2 != nil {
		cur.Next = list2
	}
	return head.Next
}

func main() {
	l1 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: nil}}}
	l2 := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 4, Next: nil}}}

	l := mergeTwoLists(l1, l2)
	for l != nil {
		fmt.Print(l.Val, "\t")
		l = l.Next
	}
	// 1       1       2       2       3       4
}
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

# 22.合并K个升序链表

1、Python

  • 逐一合并或者分治法来解决这个问题，它的思路类似于归并排序

  • 通过不断地将链表数组两两合并，可以高效地解决问题

  • 这个方法的时间复杂度同样是O(NlogK)，其中N是所有节点的总数，K是链表的数量

  • 1）合并两个链表的函数 mergeTwoLists:

    • 通过迭代比较两个链表的头节点，依次将较小的节点链接到结果链表中，直至一个链表为空
    • 然后，将剩下的链表直接链接到结果链表的尾部
    • 最后返回合并后的链表头节点

  • 2）合并K个链表的函数 mergeKLists:

    • 采用分治法递归地将链表数组一分为二，直到只剩下一个链表或者两个链表

    • 递归合并左右两部分链表，直至最终合并成一个链表

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 合并K个有序链表的函数，采用分治法
class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]

        # 递归分治，将链表数组分成两部分进行合并
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        return self.mergeTwoLists(left, right)        # 合并左右两部分

    # 合并两个有序链表的辅助函数
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)       # 定义一个虚拟头节点
        current = dummy
        while l1 and l2:          # 逐一比较两个链表的头节点，选择较小的节点链接到结果链表中
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next

        # 如果其中一个链表还有剩余，直接链接到结果链表的尾部
        if l1:
            current.next = l1
        if l2:
            current.next = l2

        # 返回合并后的链表
        return dummy.next


if __name__ == "__main__":
    # 辅助函数，用于打印链表（调试用）
    def print_list(node):
        while node:
            print(node.val, end=" -> ")
            node = node.next
        print("None")

    # 构造几个有序链表
    list1 = ListNode(1, ListNode(4, ListNode(5)))
    list2 = ListNode(1, ListNode(3, ListNode(4)))
    list3 = ListNode(2, ListNode(6))
    lists = [list1, list2, list3]

    # 合并链表
    merged_list = Solution().mergeKLists(lists)
    # 打印结果
    print_list(merged_list)
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

# 23.排序链表

输入：head = [4,2,1,3]
输出：[1,2,3,4]
1
2

1、Python

归并排序链表的步骤

  • 分割链表:

    • 使用快慢指针将链表分成两半，快指针每次走两步，慢指针每次走一步
    • 当快指针到达链表末尾时，慢指针就位于链表的中间这样可以将链表拆分成两部分

  • 递归排序:

    • 对链表的两部分递归地进行归并排序

  • 合并排序后的链表:

    • 合并两个已排序的链表合并过程类似于合并两个有序数组
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head):
        # 终止条件：当链表为空或只有一个节点时，返回该节点
        if not head or not head.next:
            return head

        # 使用快慢指针找到链表的中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 将链表从中点处断开，分为两个独立的链表
        mid = slow.next
        slow.next = None

        # 递归地对两个子链表进行排序
        left = self.sortList(head)
        right = self.sortList(mid)

        # 合并排序后的两个链表
        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 新链表的虚拟头节点
        dummy = ListNode(0)
        current = dummy

        # 合并两个有序链表
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next

        # 如果有一个链表没有遍历完，直接连接到新链表的末尾
        if l1:
            current.next = l1
        elif l2:
            current.next = l2

        return dummy.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 24.排序奇升偶降链表

输入: 1->8->3->6->5->4->7->2->NULL
输出: 1->2->3->4->5->6->7->8->NULL
1
2

1、Python

  • 分离奇偶链表：将链表分为奇数位链表和偶数位链表

  • 逆序偶数链表：将偶数位链表反转

  • 合并链表：将奇数位链表和逆序后的偶数位链表合并为一个升序链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def sortOddEvenList(self, head):
        oddList, evenList = self.partition(head)      # 分离奇数位链表和偶数位链表
        evenList = self.reverse(evenList)             # 反转偶数位链表
        return self.merge(oddList, evenList)          # 合并奇数位链表和逆序后的偶数位链表

    # 将原有链表奇数位和偶数位分解为两个链表
    def partition(self, head):
        oddHead = head                  # 奇数链表指向头结点
        evenHead = head.next            # 偶数链表指向第二个节点
        odd, even = oddHead, evenHead

        # 遍历链表，分离奇数位和偶数位节点
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = None        # 终止奇数位链表
        return [oddHead, evenHead]

    # 反转链表
    def reverse(self, head):
        l, r, cur = None, None, head        # 左指针、右指针、游标
        while cur.next != None:
            l = r                   # 左侧指针指向以前右侧指针位置
            r = cur                 # 右侧指针前进一位指向当前游标位置
            cur = cur.next          # 游标每次向前进一位
            r.next = l              # 右侧指针指向左侧实现反转
        cur.next = r                # 当跳出 while 循环时 cur(原链表最后一个元素) R(原链表倒数第二个元素)
        return cur

    # 合并两个链表
    def merge(self, l1, l2):
        head = ListNode(-1)               # head是新链表的头部
        cur = head                        # 我们维护一个cur 指针，我们需要做的是调整它的 next 指针
        while l1 and l2:                  # 我们重复以下过程，直到 l1 或者 l2 指向了 null
            if l1.val <= l2.val:     # 如果l1值小就将l1节点加到新链表后面
                cur.next = l1
                l1 = l1.next
            else:                    # 否则，我们对 l2 做同样的操作
                cur.next = l2
                l2 = l2.next
            cur = cur.next                 # 不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        cur.next = l1 if l1 is not None else l2
        return head.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# ④ 其他

# 31.重排链表

  • 143.重排链表 (opens new window)

  • 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

  • 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

  • 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
1

1、Python

  • 遍历链表，将链表每个node都放入到 list中，使用左右指针分别指向list开始和末尾位置
  • 依次将左指针的next指向右指针，左指针移动1位，然后将右指针的下一个节点执行左节点，依次反复即可
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head):
        tmp = []
        node = head
        while node:
            tmp.append(node)
            node = node.next
            
        l, r = 0, len(tmp) - 1
        while l < r:
            tmp[l].next = tmp[r]
            l = l + 1
            if l == r:            # 重合，奇数个且已经到链表中心位置
                break
            tmp[r].next = tmp[l]  # 设置右侧指针的下一个节点为左侧位置下一个节点
            r = r - 1
        tmp[l].next = None        # 此时左右指针重合，设置节点中心位置的下一个节点为None
        return head


if __name__ == "__main__":
    lst = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))  # 1-->2-->3-->4
    l = Solution().reorderList(lst)
    while l:
        print(l.val)  # 1 4 2 3
        l = l.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

2、Go

type ListNode struct {
	Val     int
	Next    *ListNode
}

func reorderList(head *ListNode)  {
	tmp := []*ListNode{}  // 创建一个列表存放节点数据
	node := head
	for node != nil {
		tmp = append(tmp, node)  // 将每个节点分别加入到列表中
		node = node.Next         // 指针向下移动一位
	}
	l,r := 0, len(tmp) - 1
	for l < r {
		tmp[l].Next = tmp[r]     // 将左指针的下一个节点设置为右指针对称位置
		l = l + 1                // 左指针向右移动一位
		// 如果左指针移动一位和右指针重合，证明节点为奇数个，此时已经到链表中心位置
		if l == r {
			break
		}
		tmp[r].Next = tmp[l]    // 设置右侧指针的下一个节点为左侧位置下一个节点
		r = r - 1               // 右指针向左移动一位
	}
	tmp[l].Next = nil           // 此时左右指针重合，设置节点中心位置的下一个节点为None
}

func main() {
	//  1-->2-->3-->4
	head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}}
	reorderList(head)

	// 1 4 2 3
	for head != nil {
		fmt.Print(head.Val, "\t")
		head = head.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
32
33
34
35
36
37

# 32.随机链表的复制

  • 138.随机链表的复制 (opens new window)

  • 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点

  • 构造这个链表的 深拷贝, 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值

  • 新节点的 next 指针和 random 指针也都应指向复制链表中的新节点

  • 并使原链表和复制链表中的这些指针能够表示相同的链表状态

  • 复制链表中的指针都不应指向原链表中的节点

1、Python

  • 通过递归方式，先拷贝链表的 next指针构成新的链表，此时新链表的 random全都是None
  • 然后回溯执行 deepCopy(node.random)从cache中获得旧链表random的复制节点，添加到新链表random指针上即可
class Node:
    def __init__(self, val=0, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head):
        cache = {}                      # 哈希表，用于存储原节点与其对应的复制节点
        def deepCopy(node):
            if node is None:            # None到达链表尾部，直接返回
                return None
            if node in cache:           # 处理random时不能重复创建，获取返回即可
                return cache[node]
            
            newNode = Node(node.val)       # 创建新节点，值与原节点相同，但next和random初始为None
            cache[node] = newNode          # 将新节点缓存起来，避免重复创建

            newNode.next = deepCopy(node.next)       # 递归复制next节点
            newNode.random = deepCopy(node.random)   # 递归复制random节点
            return newNode                           # 返回复制的新节点

        return deepCopy(head)        # 通过递归的方式拷贝链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 33.二叉树展开为链表

1、Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def flatten(self, root) -> None:
        while root:                      # 遍历整个二叉树
            if not root.left:            # 如果当前节点的左子树为空，直接跳到右子树
                root = root.right
            else:
                # 找到左子树的最右边节点
                cur = root.left
                while cur.right:
                    cur = cur.right
                    
                cur.right = root.right      # 当前节点右子树，放到当前节点左子树最右叶子的right节点下面
                root.right = root.left      # 将左子树移动到右子树的位置
                root.left = None            # 将当前节点的左子树置为空
                root = root.right           # 移动到下一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  • 变化过程:

上次更新: 2025/4/29 17:38:19
11.字符串
31.树

← 31.树→

最近更新
01
04.数组双指针排序_子数组
03-25
02
08.动态规划
03-25
03
06.回溯算法
03-25
更多文章>
Theme by Vdoing | Copyright © 2019-2025 逍遥子 技术博客 京ICP备2021005373号