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

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

问题形容：

输出一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 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
}

题目形容：

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

示例：
```
 输出: 1->2->3->4->5->NULL
输入: 5->4->3->2->1->NULL
```
限度：
- 0 <= 节点个数 <= 5000

解题思路：

暂存原 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
}

递归回溯时批改 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
}

题目形容：

请实现 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]
}

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

回顾链表

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

剑指 Offer 24. 反转链表

剑指 Offer 35. 简单链表的复制