[TOC]

代码随想录—链表

嗨嗨，越是到了期末周，越是想开摆。复习什么的，60分万岁吧。有些东西真不感兴趣了。

---

这次是来到了链表篇（毕竟链表和数组在数据结构中很是重要）

这里我基本都是使用的迭代法（递归法得慢慢修炼修炼再考虑了）

（从大一c语言学习的时候，就觉得大多数情况下都能约定好使用的是虚拟头结点就好了）

所以推荐使用链表时都使用一个虚拟头结点（力扣人好像喜欢叫哑结点）

偶尔的话可以使用哨兵结点，用于减少判断条件或者越界

先大概概括一下基本题型吧

• 链表的建立以及增删查改
  • 虚拟头结点的使用，temp临时指针等
  • 边界条件判断（什么时候使用current !=null 什么时候使用current.Next !=null)
  • 拓展： 双向链表，循环链表（记得试试约瑟夫环这个经典问题）
• 反转链表
  • 原地反转（注意使用指针保存下一个结点）
  • 新建头结点然后使用头插
• 删除链表倒数第N个结点
  • 直接暴力，第一次先算链表长度，第二次遍历删除该结点
  • 使用前后指针，先让快指针走N步，然后慢指针开始出发。
• 判断是否有环
  • 让你判断是否有环
    • 快慢指针
    • 哈希表
  • 寻找环的入口
    • 快慢指针
    • 哈希表

链表基础(创建以及增删查改)

力扣相关题目（也可以看看数据结构相关书籍，那边基础功能更多更全）

设计链表

class MyLinkedList {
    private ListNode head;
    int size;
    private static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val =val;
            this.next = null;
        }
        ListNode(){}
    }
    public MyLinkedList() {
        size=0;
        head =new ListNode(-1);
    }

    public int get(int index) {
        if(index>=size|| index<0){
            return -1;
        }
        ListNode current=head;
        int i=0;

        while(i<=index){
            current = current.next;
            i++;
        }
        return current.val;
    }

    public void addAtHead(int val) {
       addAtIndex(0,val);

    }

    public void addAtTail(int val) {
       addAtIndex(size,val);
    }

    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
         index = Math.max(0, index);
        int i=0;
        size++;
        ListNode newNode=new ListNode(val);
        ListNode current=head;
        while(i<index){
           i++;
            current=current.next;
       }
       newNode.next=current.next;
       current.next=newNode;
    }

    public void deleteAtIndex(int index) {
        if(index>=size|| index<0){
            return;
        }
        size--;
        ListNode current= head;
        int i=0;
        while(i<index){
            i++;
            current=current.next;
        }
        current.next=current.next.next;

    }
}

type ListNode struct {
	Val  int
	Next *ListNode
}

type MyLinkedList struct {
	head *ListNode
	size int
}

func Constructor() MyLinkedList {
	return MyLinkedList{&ListNode{}, 0}
}

func (l *MyLinkedList) Get(index int) int {
	if index < 0 || index >= l.size{
		return -1
	}
	current := l.head
	for i:=0;i<=index;i++{
		current = current.Next
	}
	return current.Val
}
func (l*MyLinkedList)AddAtHead(val int){
	l.AddAtIndex(0,val)
}
func (l*MyLinkedList)AddAtTail(val int){
	l.AddAtIndex(l.size,val)
}
func (l*MyLinkedList)AddAtIndex(index, val int){
	if index > l.size{
		return 
	}
	index =max(index,0)	
	//if index < 0 {
	//	index = 0
	//}
	current :=l.head
	for i:=0;i<index;i++{
		current = current.Next
	}
	l.size++
	 toAdd := &ListNode{val, current.Next}
	//toAdd.Next=current.Next
	current.Next=toAdd
}
func (l*MyLinkedList) DeleteAtIndex(index int){
	if index >=l.size || index <0{
		return 
	}
	current :=l.head
	for i:=0;i<index;i++{
		current=current.Next
	}
	l.size--
	current.Next=current.Next.Next
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

链表的反转

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode last=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return last;
    }
}

迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
   ListNode p =head.next;

   head.next=null;

   ListNode q;

   while(p!=null){
       q=new ListNode();

       q.val=p.val;

       q.next=head;

       head=q;

       p=p.next;

    }
    return head;
    }
}

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var pre *ListNode
    current := head
    for current !=nil {
        temp := current.Next
        current.Next=pre
        pre=current
        current = temp
    }
    return pre

}

删除链表倒数第N个结点

19. 删除链表的倒数第 N 个结点

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

 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    demmyHead := &ListNode{0,head}
    fast,slow := demmyHead,demmyHead
    f :=0
    for f < n {
        f++
        fast=fast.Next
    }
    for fast.Next!=nil {
        fast=fast.Next
        slow=slow.Next
    }
    slow.Next=slow.Next.Next
    return demmyHead.Next
}

链表有环判断环入口问题

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

快慢指针法

 type ListNode struct {
    Val int
    Next *ListNode 
 }

func detectCycle(head *ListNode) *ListNode {
    fast,slow := head ,head
    for fast != nil && fast.Next!=nil && fast.Next.Next!=nil{
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            fast = head 
            for fast != slow {
                    fast = fast.Next
                    slow = slow.Next
            }
            return fast
        }
    }
    return nil
    
}

哈希表法

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode current =  head;
        Set<ListNode>hashSet =new HashSet<ListNode>();
        while(current!=null){
            if(hashSet.contains(current)){
                return current;
            }else {
                hashSet.add(current);
            }
            current=current.next;
        }
        return null;
    }
}

func detectCycle(head *ListNode) *ListNode {
    hashMap := map[*ListNode]int{}
    current := head 
    for current != nil {
        if _,ok :=hashMap[current]; ok {
            return current
        }else {
            hashMap[current]=1
        }
        current = current.Next
    }
    return nil
}