剑指Offer之链表专题

链表专题

剑指Offer06.从尾到头打印链表

题目描述：

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

示例 ：

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

限制：

0 <= 链表长度 <= 10000

算法代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

//直接递归反转
func reversePrint(head *ListNode) []int {
    if head == nil {return nil}
    return append(reversePrint(head.Next) , head.Val)
}

func reversePrint(head *ListNode) []int {
    // 1.遍历链表时直接Val添加到数组头部:时间复杂度O(N) | 空间复杂度O(1)
    ans := []int{}
    for head != nil {
        ans = append([]int{head.Val}, ans...)
        head = head.Next
    }
    return ans
}

算法思路：

1. 递归法
2. 辅助栈法
3. 直接顺序获取值放到数组，再反转结果

算法改进：（数组索引）

/**
 * 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 head != nil {
        res = append(res, head.Val)
        head = head.Next
    }

    for i, j := 0, len(res)-1; i < j; {
        res[i], res[j] = res[j], res[i]
        i++
        j--
    }

    return res
}

剑指Offer24.反转链表

题目描述：

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

示例:

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

限制：

0 <= 节点个数 <= 5000

算法代码：

// 递归
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    var p = reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return p
}

算法思路：

常规的递归思路。

算法优化：

链表节点中有两个元素：

• 值
• 指针

type ListNode struct {
    Val  int
    Next *ListNode
}

Next指向下一个节点

那么这道题其实就是把指针指向前一个节点

位置调换次数	pre	cur	whole
0	nil	1->2->3->4->5	1->2->3->4->5
1	1->nil	2->-3>->4->5	2->3->4->5->1->nil
2	2->1->nil	3->4->5	3->4->5->2->1->nil
3	3->2->1->nil	4->5	4->5->3->2->1->nil
4	4->3->2->1->nil	5	5->4->3->2->1->nil

可以看出来

• pre是cur的最前面那位（pre = cur）
• cur就是当前位的后面链表元素（cur = cur.Next）
• cur.Next肯定是接pre（cur.Next = pre）

优化代码：

//反转链表的实现
func reversrList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre //这句话最重要
    }
    return pre
}

剑指Offer22.链表中倒数第k个节点

题目描述：

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

算法思路：

1. 快慢指针法：快指针先走k，然后快慢指针一起走，快指针走到终点时，慢指针即为所求。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getKthFromEnd(head *ListNode, k int) *ListNode {
    var slow , fast *ListNode = head , head
    for i := 0 ; i < k ;{
        fast = fast.Next
        i ++
    }
    if fast == nil {
        return head
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

1. 数组索引法

func getKthFromEnd(head *ListNode, k int) *ListNode {
    var res []*ListNode
    for head != nil {
        res = append(res , head)
        head = head.Next
    }
    l := len(res)
    if l >= k {
        return res[l - k]
    }

    return nil
}

以空间换时间。 空间都不大行。

1. 遍历递归

func getKthFromEnd(head *ListNode, k int) *ListNode {
    if head == nil {
        return nil
    }
    node ,_ := getKthFromEndre(head,k)
    return node
    
}

func getKthFromEndre(head *ListNode, k int) (*ListNode, int) {
    if head == nil {
        return nil,0 //遍历到最后返回0，开始往上+1判断是否等于k，等于的话直接返回node
    }
    node, res := getKthFromEndre(head.Next, k)
    if res == k {
        return node, res
    }
    res++
    return head, res
}

剑指Offer25.合并两个排序的链表

题目描述：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

解题思路：

中心思想：因为有序，则利用双指针分别指向两条链表的表头，然后通过比较大小改变这些节点的指向即可。

1. 利用一个头节点head简化合并过程。

算法代码：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode {
        Val : 0 ,
        Next : nil ,
    }
    p := head 
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            p.Next = l1
            l1 = l1.Next 
        }else {
            p.Next = l2 
            l2 = l2.Next 
        }
        p = p.Next
    }

    if l1 != nil {
        p.Next = l1 
    }
    if l2 != nil {
        p.Next = l2
    }

    return head.Next
}

剑指Offer35.复杂链表的复制

题目描述：

请实现 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 = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：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 {
    
}