LeetCode刷题计划:Day 2

回顾链表

  • 链表以节点为单位,每个元素都是一个独立对象,在内存空间的存储是非连续的。链表的节点对象具有两个成员变量:「值 val」,「后继节点引用 next」 。

    LeetCode刷题计划:Day 2_第1张图片

剑指 Offer 06. 从尾到头打印链表

  • 问题描述:

    输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

    示例1:

    输入:head = [1,3,2]
    输出:[2,3,1]

    限制:

    • 0 <= 链表长度 <= 1000
  • 解题思路:

    遍历链表时逆序保存节点的值:

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func reversePrint(head *ListNode) []int {
        if head == nil {
            return nil
        }
        res := []int{}
        for cur := head; cur != nil; cur = cur.Next {
            res = append([]int{cur.Val}, res...)
        }
        return res
    }

剑指 Offer 24. 反转链表

  • 题目描述:

    定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

    示例:

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

    限制:

    • 0 <= 节点个数 <= 5000
  • 解题思路:

    1. 暂存原Next指针,然后使当前节点指向前一个节点:

      /**
      * Definition for singly-linked list.
      * type ListNode struct {
      *     Val int
      *     Next *ListNode
      * }
      */
      func reverseList(head *ListNode) *ListNode {
       if head == nil {
           return nil
       }
       var pre *ListNode
       cur := head
       for cur != nil {
           tmp := cur.Next
           cur.Next = pre
           pre = cur
           cur = tmp
       }
       return pre
      }
    2. 递归回溯时修改Next指针:

      /**
      * Definition for singly-linked list.
      * type ListNode struct {
      *     Val int
      *     Next *ListNode
      * }
      */
      func reverseList(head *ListNode) *ListNode {
       if head == nil {
           return nil
       }
       return recur(head, nil)
      }
      
      func recur(cur *ListNode, pre *ListNode) *ListNode {
       if cur == nil {
           return pre
       }
       newHead := recur(cur.Next, cur)
       cur.Next = pre
       return newHead
      }

剑指 Offer 35. 复杂链表的复制

  • 题目描述:

    请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

    示例1:

    LeetCode刷题计划:Day 2_第2张图片

    输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

    示例2:

    LeetCode刷题计划:Day 2_第3张图片

    输入:head = [[1,1],[2,1]]
    输出:[[1,1],[2,1]]

    示例3:

    输入:head = []
    输出:[]
    解释:给定的链表为空(空指针),因此返回 null。

    提示:

    • -10000 <= Node.val <= 10000
    • Node.random 为空(null)或指向链表中的节点
    • 节点数目不超过 1000
  • 解题思路:

    维护一个哈希表,第一次遍历老链表时,保存新老链表各节点的映射;第二次遍历老链表时利用哈希表,给新链表节点的指针进行赋值:

    /**
     * Definition for a Node.
     * type Node struct {
     *     Val int
     *     Next *Node
     *     Random *Node
     * }
     */
    func copyRandomList(head *Node) *Node {
        nodeMap := make(map[*Node]*Node)
        for cur := head; cur != nil; cur = cur.Next {
            newNode := &Node{Val: cur.Val}
            nodeMap[cur] = newNode
        }
        for cur := head; cur != nil; cur = cur.Next {
            nodeMap[cur].Next = nodeMap[cur.Next]
            nodeMap[cur].Random = nodeMap[cur.Random]
        }
        return nodeMap[head]
    }

你可能感兴趣的