Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    newHead := &ListNode{}  // 新链表的头节点，带头节点不用特殊处理空链情况
    newRear := newHead  // 指向新链表的最后一个节点
    p, q := list1, list2    // 指向list1、list2
    
    for p != nil && q != nil {
        // 新链表的末尾加上p与q中的较小者
        if p.Val < q.Val {
            newRear.Next = p
            p = p.Next
            newRear = newRear.Next
            newRear.Next = nil
        } else {
            newRear.Next = q
            q = q.Next
            newRear = newRear.Next
            newRear.Next = nil
        }
    }

    if p != nil {
        newRear.Next = p
    }

    if q != nil {
        newRear.Next = q
    }
    
    // 返回结果不带头指针
    return newHead.Next
}

环形链表

环形链表

解题思路

  1. 哈希表：利用哈希表记录当前节点是否被访问过，需要额外的空间来存放哈希表，时间复杂度O(n)，空间复杂度O(n)
  2. 快慢指针：定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。时间复杂度O(n)，空间复杂度O(1)

解题代码

  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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    hashMap := make(map[*ListNode]bool)
    p := head	// 遍历指针

    for p != nil {
        if _, ok := hashMap[p]; !ok {
            // 当前节点之前没有遍历过，记录在哈希表中
            hashMap[p] = true
        } else {
            // 当前遍历的节点之前已经遍历过，说明有环
            return true
        }
        p = p.Next
    }
	
    // 每一个节点都只被遍历了一次，没有环
    return false
}
  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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    // 定义快慢指针
    slow, fast := head, head.Next

    for slow != fast {
        if fast == nil || fast.Next == nil {
            return false
        }
        slow = slow.Next    // 慢指针走一步
        fast = fast.Next.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
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrder(root *TreeNode) [][]int {
    ret := [][]int{}    // 返回结果

    if root == nil {
        return ret
    }

    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {   // 队列不空时循环
        ret = append(ret, []int{})
        p := []*TreeNode{}  // 记录下一层节点
        for j := 0; j < len(q); j++ {
            cur := q[j]
            ret[i] = append(ret[i], cur.Val)
            if cur.Left != nil {    // 左子树不为空，入队
                p = append(p, cur.Left)
            }
            if cur.Right != nil {   // 右子树不为空，入队
                p = append(p, cur.Right)
            }
        }
        q = p
    }

    return ret
}