AK F.*ing leetcode 流浪计划之链表

字节员工,直播业务长期招人(北京,杭州,上海,深圳),hc巨多,社招,校招,实习都有。
欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

@[toc]

一、简介

在leetcode里链表问题大部分是基础的模拟题,题目解题思路的理解和思考并不难,这类题目的难点在于对边界情况的考虑。面试中出这类题目,往往是考查应试者测试用例设计能力和考虑问题的全面性。想要写出准确、简短的代码,需要平时对固定的操作原理及代码了然于心,用到时做到胸有成竹,处变不惊。

本文将介绍单链表的常用操作及其应用,对于双链表部分由于题目较少,原理也与单链表类似,只介绍双链表插入部分。

由于带头结点可以简化很多边界问题,我喜欢把无头结点的链表前面加一个头结点再进行处理。

本文原理参照严版《数据结构与算法》,公众号内回复“数据结构”可以获取pdf电子版。

二、作用

  1. 链表常规操作,增,删,改,查
  2. 判断是否有环路(快慢指针)
  3. 查询倒数第K个结点(跟车算法)
  4. 综合上述基础操作,可以组合出更复杂的操作。

三、方法定义及算法

单向链表

一个结点定义为Node

type Node struct {
    Val int // 值
    Next *Node 
}

一个链表定义为List

type List struct {
    head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
  // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)

  // 常规操作
  // 初始化List
  Init(*Node)

  // 链表遍历
  Visit(func)

  // 判断是否为空
  IsEmpty()

    // 取长度
  Length()

    // 获取第i个结点
  Get(int)

    // 删除第i个结点
  Delete(int)

    // 在最前面插入结点
  InsertHead(*Node)

    // 在第i个结点之后插入结点
  Insert(int, *Node)

  // 反转链表
    Reverse()

    // 双指针相关
    // 1、取链表中间结点始第 l.Len()/2向上取整个结点
  GetMiddleNode()

    // 2、取倒数第K个结点
  GetTailKthNode(int)
}

算法详解

// 初始化:加上头结点
List::Init(node *Node) {
  head<- new(Node)
  head.Next<-node 
}

// 链表遍历
List::Visit(vis func(*Node)) {
  for node <- head to tail {
    vis(node)
  }
}

// 判断是否为空
List::IsEmpty() bool {
  return head.Next==NULL
}

// 取长度
List::Length() int {
  len<-0 
  for node <- head to tail {
    len<-len+1
  }
  return len
}

// 获取第i个结点
List::Get(i int) *Node {
  cur<-head 
  while(i>0 && cur!=NULL) {
    i<-i-1
    cur<-cur.Next
  }

  return cur
}

查找第i个结点并删除

pre最终指向了第i个结点的前一个结点,这样子才方便删除。

删除时直接把Pre.Next指向elem.Next即可。

// 删除第i个结点 如图动画
List::Delete(i int) *Node {
  pre<-head // 定义pre 最终指向第i个结点的前一个结点
  i<-i-1 // 实际实现中用Get(i-1)
  while(i>0 && pre!=NULL) {
    i<-i-1
    pre<-pre.Next
  }

  if pre==NULL || pre.Next==NULL {
    // i已经超出了范围无效
    return NULL
  }
  elem <- pre.Next
  pre.Next<-pre.Next.Next
  return elem
}

插入在第1个位置

1,2 顺序不可调换。 根据贪心原理,我们始终要能够访问到7这个结点,要是调换顺序,7将访问不到了。

// 在最前面插入结点, 即在head后面插入一个元素
List::InsertHead(elem *Node) {
  elem.Next<-head.Next
  head.Next<-elem
}

在第i个位置插入

查找第i个结点与删除算法类似,区别是i不用减1了,因为这次找的就是第i个结点,之前找的是第i个结点的前一个。插入方法与插入前端位置相同。

// 在第i个结点之后插入结点, 查找第i个结点与删除算法类似
List:: Insert(i int, elem *Node) {
  pre<-head // 定义pre 最终指向第i个结点,实际实现中用Get(i)
  while(i>0 && pre!=NULL) {
    i<-i-1
    pre<-pre.Next
  }

  if pre==NULL {
    // i已经超出了范围无效
    return
  }
  elem.Next<-pre.Next
  pre.Next<-elem
}




    // 反转链表, 可以采用头插法
    List::Reverse() {
        pre<-head.Next
        head.Next=NULL
        while(pre!=NULL) { // 依次遍历
            temp<-pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。
            pre<-pre.Next
            InsertHead(temp)
        }
    }
中间结点位置 链表长度
1 1,2
2 3,4
3 5,6
4 7,8
5 9,10
n n2-1, n\2
    // 1、取链表中间结点始第 l.Len()/2向上取整个结点,
    List::GetMiddleNode() *Node{
        if head.Next==NULL {
            return NULL
        }
        first<-head // 每次走一步
        second<-head // 每次走2步
        /*
        从上表可以看出
        second走到奇数位时,first就要走一步。
        */
        while(second!=NULL) {
            second<-second.Next
            if second!=NULL { // 只要second能走出一步(奇数位),first就往后走
                first<-first.Next
                second<-second.Next
            }
            // 如果是向下取整则是second走2步后first走1步
            // if second!=NULL {first<-first.Next}
        }

        return first
    }

倒数第K个结点与末尾关系

利用双指针跟车算法,当last指向nil时,tailKth刚好指向倒数第K个结点。

可以先让last指向第K个结点。然后tailKth指向head。接着同时往前移,直到last=nil。

    // 2、取倒数第K个结点,跟车算法
    List::GetTailKthNode(k int) *Node{
        last<-Get(k)
        if last==NULL {// length<k
            return NULL
        }
        tailKth<-head
        while(last!=NULL) {
            last<-last.Next
            tailKth<-tailKth.Next
        }
        return tailKth
    }

双向非循环链表

一个结点定义为Node

type Node struct {
    Val int // 值
    Next, Prev *Node
}

一个双向链表定义为DuList

type DuList struct {
    head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
  // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)

  // 常规操作
     // 删除第i个结点
  Delete(int)

    // 在最前面插入结点
  InsertHead(*Node)
}

算法详解

删除第i个结点

elem为第i个元素,红线为前后指针,由于制作中不会对红线进行制作,所以7,2结点是一直都可以访问到的。图中是先改变7的后续结点,再改变2的前续结点,相反的顺序也是可以的。
注意elem没有后续的情况

// 删除第i个结点
DuList::Delete(i int) *Node {
  elem<-head
  while(i>0 && elem!=null) {
    i<-i-1
    elem<-elem.Next
  }
  if elem==NULL { // i 太大了
    return NULL
  }
  elem.Prev.Next<-elem.Next
  if elem.Next!=NULL {
      elem.Next.Prev<-elem.Prev
  }
  return elem
}

在这里插入图片描述

这里的关键点在于,2有可能是访问不到的,所以优先把2相关的操作都做完,后面的就没有风险了。

注意要判断head.Next是否为空

// 在最前面插入结点
DuList::InsertHead(*Node) {
  elem.Next<-head.Next
  if elem.Next!=NULL {
      elem.Next.Prev<-elem
  }
  head.Next<-elem
  elem.Prev<-head
}

四、具体实现

单链表

package main

import "fmt"

type Node struct {
    Val        int // 值
    Next, Prev *Node
}

type List struct {
    head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *List) Init(node *Node) {
    l.head = &Node{Val: 0, Next: node}
}

// 数组初始化
func (l *List) InitArr(arr ...int) {
    l.Init(nil)
    tail := l.head
    for _, n := range arr {
        tail.Next = &Node{Val: n}
        tail = tail.Next
    }
}

// 链表遍历
func (l *List) Visit(vis func(*Node)) {
    for cur := l.head.Next; cur != nil; cur = cur.Next {
        vis(cur)
    }
}

// 判断是否为空
func (l *List) IsEmpty() bool {
    return l.head.Next == nil
}

// 取长度
func (l *List) Length() int {
    sum := 0
    l.Visit(func(node *Node) {
        sum++
    })
    return sum
}

// 获取第i个结点
func (l *List) Get(i int) *Node {
    cur := l.head
    for ; i > 0 && cur != nil; i, cur = i-1, cur.Next {
    }
    return cur
}

// 删除第i个结点
func (l *List) Delete(i int) *Node {
    pre := l.Get(i - 1)
    if pre == nil || pre.Next == nil {
        // i已经超出了范围无效
        return nil
    }
    elem := pre.Next
    pre.Next = pre.Next.Next
    return elem
}

// 在最前面插入结点
func (l *List) InsertHead(elem *Node) {
    elem.Next = l.head.Next
    l.head.Next = elem
}

// 在第i个结点之后插入结点
func (l *List) Insert(i int, elem *Node) {
    pre := l.Get(i) // 定义pre 最终指向第i个结点,实际实现中用Get(i)
    if pre == nil {
        // i已经超出了范围无效
        return
    }
    elem.Next = pre.Next
    pre.Next = elem
}

// 反转链表, 可以采用头插法
func (l *List) Reverse() {
    pre := l.head.Next
    l.head.Next = nil
    for pre != nil { // 依次遍历
        temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。
        pre = pre.Next
        l.InsertHead(temp)
    }
}

// 双指针相关
// 1、取链表中间结点始第 l.Len()/2向上取整个结点
func (l *List) GetMiddleNode() *Node {
    if l.head.Next == nil {
        return nil
    }
    first := l.head  // 每次走一步
    second := l.head // 每次走2步
    /*
        从上表可以看出
        second走到奇数位时,first就要走一步。
    */
    for second != nil {
        second = second.Next
        if second != nil { // 只要second能走出一步(奇数位),first就往后走
            first = first.Next
            second = second.Next
        }
        // 如果是向下取整则是second走2步后firt走1步
        // if second!=NULL {first<-first.Next}
    }

    return first
}

// 2、取倒数第K个结点
func (l *List) GetTailKthNode(k int) *Node {
    last := l.Get(k)
    if last == nil { // length<k
        return nil
    }
    tailKth := l.head
    for ; last != nil; last, tailKth = last.Next, tailKth.Next {
    }
    return tailKth
}

func main() {
    arr := []int{2, 3, 4, 5, 6, 7, 7, 8, 8}
    // InitArr 测试
    fmt.Println("InitArr 测试")
    l := &List{}
    l.InitArr(arr...)
    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println()

    fmt.Println("InitArr 测试 end")
    fmt.Println("--------------------------")
    fmt.Println("Init 测试")
    l.Init(l.head.Next)
    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println()

    fmt.Println("Init 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("IsEmpty 测试")
    fmt.Println(l.IsEmpty())
    l.Init(nil)
    fmt.Println(l.IsEmpty())
    fmt.Println()

    fmt.Println("IsEmpty 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("Length 测试")
    fmt.Println(l.Length())
    for i := 1; i < 10; i++ {
        l.InsertHead(&Node{Val: i})
        fmt.Println(l.Length())
    }
    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })

    fmt.Println("\nLength 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("Get 测试")
    fmt.Println(l.Length())
    for i := 1; i < 11; i++ {
        node := l.Get(i)
        fmt.Printf("%+***", node, node)
    }

    fmt.Println("\nGet 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("Delete 测试")
    fmt.Println(l.Length())
    node := l.Delete(11)
    fmt.Printf("%+***", node, node)
    node = l.Delete(9)
    fmt.Printf("%+***", node, node)
    node = l.Delete(8)
    fmt.Printf("%+***", node, node)
    node = l.Delete(2)
    fmt.Printf("%+***", node, node)
    node = l.Delete(1)
    fmt.Printf("%+***", node, node)
    node = l.Delete(5)
    fmt.Printf("%+***", node, node)

    fmt.Println("\nDelete 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("InsertHead 测试")

    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println()
    l.InsertHead(&Node{Val: 100})
    l.InsertHead(&Node{Val: 101})
    l.InsertHead(&Node{Val: 99})

    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println("\nInsertHead 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("InsertHead 测试")

    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println()
    l.Insert(1, &Node{Val: 1100})
    l.Insert(3, &Node{Val: 1101})
    l.Insert(2, &Node{Val: 199})

    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println("\nInsertHead 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("Reverse 测试")

    l.Reverse()
    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println()
    l.Reverse()
    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })

    fmt.Println("\nReverse 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("GetMiddleNode 测试")

    l.Init(nil)
    fmt.Printf("%+***", l.GetMiddleNode(), l.GetMiddleNode())
    for i := 1100; i < 1111; i++ {
        l.InsertHead(&Node{Val: i})
        fmt.Printf("%+***", l.GetMiddleNode(), l.GetMiddleNode())
        fmt.Printf("%+v\n", l.Get((l.Length()+1)/2))
        l.Visit(func(node *Node) {
            fmt.Printf(", %d", node.Val)
        })
        fmt.Println("len:", l.Length())
    }

    fmt.Println("\nGetMiddleNode 测试 end")
    fmt.Println("--------------------------")

    fmt.Println("GetTailKthNode 测试")

    l.Visit(func(node *Node) {
        fmt.Printf(", %d", node.Val)
    })
    fmt.Println("len:", l.Length())

    node = l.GetTailKthNode(15)
    fmt.Printf("%+***", node, node)
    for i := 1; i <= l.Length(); i++ {
        node := l.GetTailKthNode(i)
        fmt.Printf("%+***", node, node)
    }

    fmt.Println("\nGetTailKthNode 测试 end")
    fmt.Println("--------------------------")
}

双链表

package main

import "fmt"

type Node struct {
    Val        int // 值
    Next, Prev *Node
}

type DuList struct {
    head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *DuList) Init(node *Node) {
    l.head = &Node{Val: 0, Next: node}
    if node != nil {
        node.Prev = l.head
    }
}

// 数组初始化
func (l *DuList) InitArr(arr ...int) {
    l.Init(nil)
    tail := l.head
    for _, n := range arr {
        tail.Next = &Node{Val: n}
        tail.Next.Prev = tail
        tail = tail.Next
    }
}

// 链表遍历
func (l *DuList) Visit(vis func(*Node)) {
    for cur := l.head.Next; cur != nil; cur = cur.Next {
        fmt.Printf("%d, ", cur.Val)
        if vis != nil {
            vis(cur)
        }
    }
    fmt.Println()
}

// 链表遍历
func (l *DuList) VisitReverse() {
    tail := l.head
    for cur := l.head.Next; cur != nil; cur = cur.Next {
        tail = cur
        fmt.Printf("%d, ", cur.Val)
    }
    fmt.Println("reverse")
    for ;tail != nil && tail != l.head;tail = tail.Prev {
        fmt.Printf("%d, ", tail.Val)
    }
    fmt.Println("")
}

// 取长度
func (l *DuList) Length() int {
    sum := 0
    l.Visit(func(node *Node) {
        sum++
    })
    return sum
}

// 删除第i个结点
func (l *DuList) Delete(i int) *Node {
    elem := l.head
    for ; i > 0 && elem != nil; i, elem = i-1, elem.Next {
    }
    if elem == nil { // i 太大了
        return nil
    }
    elem.Prev.Next = elem.Next
    if elem.Next!=nil {
        elem.Next.Prev = elem.Prev
    }
    return elem
}

// 在最前面插入结点
func (l *DuList) InsertHead(elem *Node) {
    elem.Next = l.head.Next
    if elem.Next != nil {
        elem.Next.Prev = elem
    }

    l.head.Next = elem
    elem.Prev = l.head
}

func main() {
    arr := []int{2, 3, 4, 5, 6, 7, 7, 8, 8}

    l := &DuList{}
    fmt.Println("InitArr 测试")
    l.InitArr(arr...)
    l.Visit(nil)
    l.VisitReverse()
    fmt.Println()

    fmt.Println("InitArr 测试 end")
    fmt.Println("--------==============-------------")


    fmt.Println("Delete 测试")
    for ;l.head.Next!=nil; {
        fmt.Printf("%+v\n",l.Delete(1))
        l.VisitReverse()
        fmt.Println()
    }

    fmt.Println("Delete 测试 end")
    fmt.Println("--------==============-------------")


    fmt.Println("InsertHead 测试")
    l.Init(nil)
    for i:=1;i<11;i++ {
        l.InsertHead(&Node{Val:i})
        l.VisitReverse()
        fmt.Println()
    }

    fmt.Println("InsertHead 测试 end")
    fmt.Println("--------==============-------------")
}

五、牛刀小试

练习1 倒数第K个结点应用

题目链接 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目大意

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:

输入:head = [1], n = 1
输出:[]
示例 3:

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

提示:

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题目解析

可以利用查找倒数第K个方法,找到倒数第K个结点的前一个。然后进行删除。

AC代码

type ListNode struct {
    Val  int // 值
    Next *ListNode
}

type List struct {
    head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *List) Init(node *ListNode) {
    l.head = &ListNode{Val: 0, Next: node}
}

// 链表遍历
func (l *List) Visit(vis func(*ListNode)) {
    for cur := l.head.Next; cur != nil; cur = cur.Next {
        vis(cur)
    }
}

// 获取第i个结点
func (l *List) Get(i int) *ListNode {
    cur := l.head
    for ; i > 0 && cur != nil; i, cur = i-1, cur.Next {
    }
    return cur
}

// 2、取倒数第K个结点
func (l *List) GetTailKthNode(k int) (pre, tailKth *ListNode) {
    last := l.Get(k)
    if last == nil { // length<k
        return nil, nil
    }
    tailKth = l.head
    for ; last != nil; last, tailKth = last.Next, tailKth.Next {
        pre = tailKth
    }
    return pre, tailKth
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    l := &List{}
    l.Init(head)
    pre, tailKth := l.GetTailKthNode(n)
    pre.Next = tailKth.Next
    return l.head.Next
}

练习2 反转链表

题目链接:https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/,https://leetcode-cn.com/problems/reverse-linked-list/

题目大意

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

示例:

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

限制:

0 <= 节点个数 <= 5000

题目解析

利用头插法反转链表。

AC代码

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

type List struct {
    head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    // tail *Node // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *List) Init(node *ListNode) {
    l.head = &ListNode{Val: 0, Next: node}
}

// 在最前面插入结点
func (l *List) InsertHead(elem *ListNode) {
    elem.Next = l.head.Next
    l.head.Next = elem
}

// 反转链表, 可以采用头插法
func (l *List) Reverse() {
    pre := l.head.Next
    l.head.Next = nil
    for pre != nil { // 依次遍历
        temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。
        pre = pre.Next
        l.InsertHead(temp)
    }
}

func reverseList(head *ListNode) *ListNode {
    l := &List{}
    l.Init(head)
    l.Reverse()
    return l.head.Next
}

练习3 奇偶链表

题目链接:https://leetcode-cn.com/problems/odd-even-linked-list/

题目大意

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

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

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:

应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

题目解析

遍历整个链表,将奇数节点收集到一个链表,将偶数结点收集到另一个链表,最后把偶数链表的头放到数链表的尾巴上。

AC代码

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

type List struct {
    head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    tail *ListNode // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *List) Init(node *ListNode) {
    l.head = &ListNode{Val: 0, Next: node}
    l.tail=l.head
}

// 在最后面添加
func (l *List) AddTail(elem *ListNode) {
    l.tail.Next = elem
    l.tail = l.tail.Next
    l.tail.Next = nil // 删除关联的尾巴
}

func oddEvenList(head *ListNode) *ListNode {
    oddList, evenList := &List{}, &List{}
    oddList.Init(nil)
    evenList.Init(nil)

    for head != nil {
        temp := head
        head = head.Next
        // 添加到奇数链表
        oddList.AddTail(temp)

        if head != nil {
            // 添加偶数链表
            temp, head = head, head.Next
            evenList.AddTail(temp)
        }
    }
    oddList.tail.Next = evenList.head.Next

    return oddList.head.Next
}

练习4 回文链表

题目链接:https://leetcode-cn.com/problems/palindrome-linked-list/

题目大意

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

题目解析

先将链表分成2半,将后一半链表反转,遍历判断是否相等。

注意奇数个元素的情况

AC代码

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

type List struct {
    head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。
    // tail *ListNode // 如果想实现一个队列也可以定义tail 来实现
    // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1)
}

// 常规操作
// 初始化List
func (l *List) Init(node *ListNode) {
    l.head = &ListNode{Val: 0, Next: node}
}

// 在最前面插入结点
func (l *List) InsertHead(elem *ListNode) {
    elem.Next = l.head.Next
    l.head.Next = elem
}

// 反转链表, 可以采用头插法
func (l *List) Reverse() {
    pre := l.head.Next
    l.head.Next = nil
    for pre != nil { // 依次遍历
        temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。
        pre = pre.Next
        l.InsertHead(temp)
    }
}


// 双指针相关
// 1、取链表中间结点始第 l.Len()/2向上取整个结点
func (l *List) GetMiddleNode() *ListNode {
    if l.head.Next == nil {
        return nil
    }
    first := l.head  // 每次走一步
    second := l.head // 每次走2步
    /*
        从上表可以看出
        second走到奇数位时,first就要走一步。
    */
    for second != nil {
        second = second.Next
        if second != nil { // 只要second能走出一步(奇数位),first就往后走
            first = first.Next
            second = second.Next
        }
        // 如果是向下取整则是second走2步后firt走1步
        // if second!=NULL {first<-first.Next}
    }

    return first
}

func isPalindrome(head *ListNode) bool {
    if head == nil {return true}
    firstHalf, secondHalf := &List{}, &List{}
    firstHalf.Init(head)

    mid := firstHalf.GetMiddleNode() // mid后边属于secondHalf, firstHalf个数 总是大于或等于secondHalf
    secondHalf.Init(mid.Next)
    mid.Next=nil // 断开前后2半
    secondHalf.Reverse()

    for fh, sh := firstHalf.head.Next, secondHalf.head.Next; fh!=nil && sh !=nil; fh, sh = fh.Next, sh.Next{
        if fh.Val!=sh.Val {return false}
    }

    return true    
}

六、总结

主要内容:

  1. 在leetcode里链表问题大部分是基础的模拟题,这类题目的难点在于对边界情况的考虑。想要写出准确、高效的代码,需要平时对固定的操作原理及代码了然于心,用到时做到胸有成竹,处变不惊。
  2. 介绍了链表基础操作和原理。
  3. 通过练习加强对链表操作的理解,大部分难的题目都是对于基础操作的组合应用。

笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。

下面我精心准备了几个题目,供大家练习参考。干他F.*ing (Fighting?)。

七、实战训练

代码基础训练题

光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那2题A了。

  1. 倒数第K个结点应用 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
  2. 反转链表 题目链接 https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/,https://leetcode-cn.com/problems/reverse-linked-list/
  3. 奇偶链表 题目链接:https://leetcode-cn.com/problems/odd-even-linked-list/
  4. 双指针取中间值 回文链表 题目链接:https://leetcode-cn.com/problems/palindrome-linked-list/

AK leetcode

leetcode相关题目都在下面了,拿起武器挨个点名呗。

https://leetcode-cn.com/tag/linked-list/problemset/ 链表题目列表


本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

#字节跳动##内推##校招##实习##社招#
全部评论

相关推荐

点赞 2 评论
分享
牛客网
牛客企业服务