1. 链表反转
来源：Leetcode 206
方法一：迭代法(头节点插入法)
思路：创建一个节点dummy，总是用来标识一个新的链表的头节点，把源链表每一次循环脱落的节点，添加到dummy.Next中，最后新建的链表就是反转后的链表
func reverseList(head *ListNode) *ListNode {
var dummy = &ListNode{}
var next = &ListNode{}
for head!= nil {
next = head.Next
head.Next = dummy.Next
dummy.Next = head
head = next
}
return dummy.Next //dummy指向的下一个节点开始才是真正的链表反转值
}
//执行用时 : 4 ms, 在Reverse Linked List的Go提交中击败了91.80% 的用户
//内存消耗 : 2.6 MB, 在Reverse Linked List的Go提交中击败了53.21% 的用户
方法二：迭代法-就地反转
思路：把当前节点的下一个节点插入到dummy的下一个节点，就地反转
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}
var dummy = &ListNode{Val:-1,Next:head}
var prev = head
var next = head.Next
for next != nil {
prev.Next = next.Next
next.Next = dummy.Next
dummy.Next = next
next = prev.Next
}
return dummy.Next
}
//执行用时 : 4 ms, 在Reverse Linked List的Go提交中击败了91.80% 的用户
//内存消耗 : 2.6 MB, 在Reverse Linked List的Go提交中击败了52.52% 的用户
2. 查找链表中间节点
来源：Leetcode 876
方法：快慢指针法
思路：设置两个指针slow,fast，分别标识快慢指针，每一次slow前进一个节点，fast都将双倍速度前进。则fast到链表末尾时，slow处于中间位置
func middleNode(head *ListNode) *ListNode {
var fast,slow *ListNode
fast,slow = head,head
for fast != nil {
if fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}else{
break
}
}
return slow
}
//执行用时 : 0 ms, 在Middle of the Linked List的Go提交中击败了100.00% 的用户
//内存消耗 : 2 MB, 在Middle of the Linked List的Go提交中击败了40.00% 的用户
3. 查找链表倒数第 k 个结点
来源：Leetcode 19
方法：间隔指针法
思路：设置指针ahead,rear，分别标识处于前方和后方的指针，两者间隔k，故当ahead到达链表末尾，rear处于K节点位置，删除rear即可
func removeNthFromEnd(head *ListNode, n int) *ListNode {
var dummy = &ListNode{-1,head}
var ahead,rear = dummy,dummy
//ahead先行n个单位
for i:=0;i<n;i++{
if ahead != nil {
ahead = ahead.Next
}else{
break
}
}
//ahead和rear同步
for ahead.Next != nil {
ahead = ahead.Next
rear = rear.Next
}
//删除节点
rear.Next = rear.Next.Next
return dummy.Next
}
//执行用时 : 4 ms, 在Remove Nth Node From End of List的Go提交中击败了93.49% 的用户
//内存消耗 : 2.2 MB, 在Remove Nth Node From End of List的Go提交中击败了87.56% 的用户
4. 逆序打印链表
来源：牛客网-《剑指Offer》第3题
名称：从尾到头打印链表
题目内容：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList
方法：递归
思路：简单的递归思想，直接深入到链表末尾，然后输出
func printListFromTailToHead(head *ListNode) []int {
var arr []int
if head == nil {
return nil
}
res := printListFromTailToHead(head.Next)
arr = append(arr,res...)
return arr
}
5. 判断一个链表是否有环
来源：Leetcode 141
方法一：map映射法
思路：将链表节点的地址作为键名，写入map，每一次判断键名是否存在，若存在，则必定在该点闭合成环
func hasCycle(head *ListNode) bool {
var list = make(map[*ListNode]int)
var cp = head
for cp != nil {
//判断是否已经经过该点
if v,ok := list[cp];!ok {
//没有经过
list[cp] = v
cp = cp.Next
}else {
//经过了，表明已经闭合
return true
}
}
return false
}
//执行用时 : 20 ms, 在Linked List Cycle的Go提交中击败了26.34% 的用户
//内存消耗 : 6.4 MB, 在Linked List Cycle的Go提交中击败了5.40% 的用户
方法一：快慢指针法
思路：将链表节点的地址作为键名，写入map，每一次判断键名是否存在，若存在，则必定在该点闭合成环
func hasCycle(head *ListNode) bool {
if head == nil || head.Next == nil {
return false
}
var fast,slow = head,head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}
//执行用时 : 12 ms, 在Linked List Cycle的Go提交中击败了94.44% 的用户
//内存消耗 : 4 MB, 在Linked List Cycle的Go提交中击败了30.16% 的用户
6. 相交链表
来源：Leetcode 160
方法一：map映射
思路：定义类型 map[*ListNode]int 键名存储节点的地址，第一次循环将headA的节点地址写入map中，第二次遍历headB时，直接判断map中是否存在 节点地址，存在则输出。
复杂度：O(n) 时间复杂度，O(n) 空间复杂度
func getIntersectionNode(headA, headB *ListNode) *ListNode {
//利用map
var ma = make(map[*ListNode]int)
var a = headA
//地址写入
for a != nil {
ma[a] = a.Val
a = a.Next
}
//判断
var b = headB
for b != nil {
if _,ok := ma[b];ok{
return b
}else{
b = b.Next
}
}
return nil
}
//执行用时 : 96 ms, 在Intersection of Two Linked Lists的Go提交中击败了30.84% 的用户
//内存消耗 : 6.4 MB, 在Intersection of Two Linked Lists的Go提交中击败了86.94% 的用户
7. 合并两个有序链表
来源：Leetcode 21
方法一：递归合并
思路：新建一个节点dummy用来标识某一个最小的链表头，每一次递归新生成的dummy的 Next 都等于再次递归生成的dummy
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
//递归返回条件
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var dummy = &ListNode{}
if l1.Val < l2.Val {
dummy = l1
dummy.Next = mergeTwoLists(l1.Next,l2)
}else {
dummy = l2
dummy.Next = mergeTwoLists(l1,l2.Next)
}
return dummy
}
//执行用时 : 4 ms, 在Merge Two Sorted Lists的Go提交中击败了98.69% 的用户
//内存消耗 : 2.6 MB, 在Merge Two Sorted Lists的Go提交中击败了21.53% 的用户
方法二：循环合并
思路：定义一个浮动节点dummy来指定每一次l1和l2比较后返回的节点，定义一个head节点标识dummy浮动的头部，每次都将dummy.Next指向l1和l2比较后的小者，后浮动dummy指向下一个节点，依次循环
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
//循环合并
var dummy = &ListNode{}
var head = dummy
for l1 !=nil && l2 != nil {
if l1.Val <= l2.Val {
dummy.Next = l1
l1 = l1.Next
}else {
dummy.Next = l2
l2 = l2.Next
}
dummy = dummy.Next
}
if l1 == nil {
dummy.Next = l2
}else {
dummy.Next = l1
}
return head.Next
}
//执行用时 : 8 ms, 在Merge Two Sorted Lists的Go提交中击败了50.58% 的用户
//内存消耗 : 2.5 MB, 在Merge Two Sorted Lists的Go提交中击败了93.30% 的用户
8. 请判断一个链表是否为回文链表
来源：Leetcode 234 《回文链表》
方法一：container/list模拟栈操作
思路：获取链表长度，链表前半部分入栈，后半部分与出栈元素比较
复杂度：O(n) 时间复杂度，O(n) 空间复杂度
func isPalindrome(head *ListNode) bool {
//特殊情况
if head == nil || head.Next == nil {
return true
}
//用栈 list模拟栈 前半段入栈
var stk = list.New()
//获得长度 快慢指针法
var slow,fast = head,head
stk.PushBack(slow.Val)
//指针开始浮动
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
stk.PushBack(slow.Val)
}
stk.Remove(stk.Back())
var cp = slow
//奇数个节点 调整
if fast != nil {
cp = cp.Next
}
//出栈元素开始与链表后半部分比较
for cp != nil {
if stk.Back().Value != cp.Val {
//不匹配 直接返回
return false
}else {
//匹配，消项处理
stk.Remove(stk.Back())
cp = cp.Next
}
}
return true
}
//执行用时 : 28 ms, 在Palindrome Linked List的Go提交中击败了69.44% 的用户
//内存消耗 : 6.1 MB, 在Palindrome Linked List的Go提交中击败了58.20% 的用户
方法二：快慢双指针+链表反转
思路：用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题。需要用到双指针+链表反转，反正我们上面已经知道了如何反转链表，和利用快慢指针进行链表操作。将慢指针指向链表中央，往后的链表节点反转，再从头开始，比对链表头节点和中央往后的节点。
func isPalindrome(head *ListNode) bool {
//特殊情况
if head == nil || head.Next == nil {
return true
}
//指定快慢指针
var slow,fast = head,head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
//备份中间节点
var cp,comp = slow,slow
//链表反转
if fast != nil {
//奇数长度的链表 往后错位一个
cp = cp.Next
}
var dummy = &ListNode{}
var next = &ListNode{}
for cp != nil {
next = cp.Next
cp.Next = dummy.Next
dummy.Next = cp
cp = next
}
//反转完毕，开始比对
dummy = dummy.Next
for head != comp {
if head.Val != dummy.Val {
return false
}else {
head = head.Next
dummy = dummy.Next
}
}
return true
}
//执行用时 : 24 ms, 在Palindrome Linked List的Go提交中击败了96.11% 的用户
//内存消耗 : 6.1 MB, 在Palindrome Linked List的Go提交中击败了58.20% 的用户
方法三：数组
思路：将所有节点值压入数组，比较索引i与len()-1-i的大小
func isPalindrome(head *ListNode) bool {
s := make([]int, 0, 100)
for {
if head == nil {
break
}
s = append(s, head.Val)
head = head.Next
}
for i := 0; i < len(s)/2; i++ {
if s[i] != s[len(s)-1-i] {
return false
}
}
return true
}
9. 删除排序链表中的重复元素
来源：Leetcode 83
方法：前后比较法
思路：定义一个间隔指针pre指向当前操作节点的前面
func deleteDuplicates(head *ListNode) *ListNode {
//只有一个元素或空链表
if head == nil || head.Next == nil {
return head
}
var pre,node = head,head.Next
var dummy = pre
//开始比对删除元素
for node != nil {
if pre.Val == node.Val {
node = node.Next
pre.Next = node
}else {
pre = node
node = node.Next
}
}
return dummy
}
//执行用时 : 8 ms, 在Remove Duplicates from Sorted List的Go提交中击败了93.24% 的用户
//内存消耗 : 3.1 MB, 在Remove Duplicates from Sorted List的Go提交中击败了59.12% 的用户