关于leetcode:LeetCode刷题计划Day-2

回顾链表

• 链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非间断的。链表的节点对象具备两个成员变量：「值 val」，「后继节点援用 next」。

剑指 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：

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

  示例 2：

   输出：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]
  }