回顾链表

  • 链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非间断的。链表的节点对象具备两个成员变量：「值 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]}