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

LightningBilly · 2021 年5 月 9 日 14:58

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

一、简介

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

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

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

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

二、作用

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

三、方法定义及算法

单向链表

一个结点定义为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, n2

	// 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
	}

利用双指针跟车算法，当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("%+v, %p\n", node, node)
	}

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

	fmt.Println("Delete 测试")
	fmt.Println(l.Length())
	node := l.Delete(11)
	fmt.Printf("%+v, %p\n", node, node)
	node = l.Delete(9)
	fmt.Printf("%+v, %p\n", node, node)
	node = l.Delete(8)
	fmt.Printf("%+v, %p\n", node, node)
	node = l.Delete(2)
	fmt.Printf("%+v, %p\n", node, node)
	node = l.Delete(1)
	fmt.Printf("%+v, %p\n", node, node)
	node = l.Delete(5)
	fmt.Printf("%+v, %p\n", 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("%+v, %p \n", l.GetMiddleNode(), l.GetMiddleNode())
	for i := 1100; i < 1111; i++ {
		l.InsertHead(&Node{Val: i})
		fmt.Printf("%+v, %p \n", 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("%+v, %p\n", node, node)
	for i := 1; i <= l.Length(); i++ {
		node := l.GetTailKthNode(i)
		fmt.Printf("%+v, %p\n", 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个结点应用

题目链接力扣

题目大意

给你一个链表，删除链表的倒数第 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 反转链表

题目链接：力扣

题目大意

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

示例:

输入: 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 奇偶链表

题目链接：力扣

题目大意

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

请尝试使用原地算法完成。你的算法的空间复杂度应为 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 回文链表

题目链接：力扣

题目大意

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

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

六、总结

主要内容：

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

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

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

七、实战训练

代码基础训练题

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

倒数第K个结点应用力扣
反转链表题目链接力扣
奇偶链表题目链接：力扣
双指针取中间值回文链表题目链接：力扣

AK leetcode

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

力扣链表题目列表

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

在这里插入图片描述