203.移除链表元素

给你一个链表的头节点 head 和一个整数 val, 请你删除链表中所有满足Node.val =val的节点，并返回新的头节点

# 实例 1:
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

# 示例 2：
输入：head = [], val = 1
输出：[]

# 示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

func removeElements(head *ListNode, val int) *ListNode {
    // 创建一个虚拟节点
    dummyHead := &ListNode{}
    // 使得虚拟结点中的next指向头结点,形成虚拟头结点
    dummyHead.Next = head
    // 因为删除元素要支持这个元素上一个元素的指针
    cur := dummyHead
    for cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        }else {
            cur = cur.Next
        }
    }
	// 返回的虚拟头结点的Next,因为head有可能会被删了
    return dummyHead.Next
}

704.设计链表

707. Design Linked List - 力扣（LeetCode）

需要再链表中实现以下功能:

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

1. 单链表

// 定义链表
type SingleNode struct {
	Val  int         // 节点的值
	Next *SingleNode // 下一个节点的指针
}

type MyLinkedList struct {
	dummyHead *SingleNode // 虚拟头节点
	Size      int         // 链表大小
}

// 构建链表
func Constructor() MyLinkedList {
	newNode := &SingleNode{ // 创建节点
		Val:  0,
		Next: nil,
	}
	return MyLinkedList{
		dummyHead: newNode, // 返回链表
		Size:      0,
	}
}

func (this *MyLinkedList) Get(index int) int {
	// 首先判断索引是否合法
	if this == nil || index < 0 || index >= this.Size { // 如果索引无效则返回-1
		return -1
	}

	// cur = 虚拟头结点
	cur := this.dummyHead
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	return cur.Next.Val
}

func (this *MyLinkedList) AddAtHead(val int) {
	// 创建新节点
	newNode := &SingleNode{
		Val: val,
	}
	// 新节点指向当前头结点
	newNode.Next = this.dummyHead.Next
	// 新节点变为头节点
	this.dummyHead.Next = newNode
	this.Size++
}

func (this *MyLinkedList) AddAtTail(val int) {
	// 创建新节点
	newNode := &SingleNode{
		Val: val,
	}
	//遍历到最后一个节点
	cur := this.dummyHead
	for cur.Next != nil {
		cur = cur.Next
	}
	// 循环结束说明指针已经指向 val (val -> nil) 这个位置了
	cur.Next = newNode
	this.Size++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	// 首先判断索引是否合法
	if index < 0 {
		index = 0
	} else if index > this.Size {
		return
	}
	// 要遍历到 Index 前一个位置
	NewNode := &SingleNode{
		Val: val,
	}
	cur := this.dummyHead
	// 遍历到指定索引前一个节点
	// val(0) -> val(1) -> target(2)
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	// 目前指针停留在 1 号索引
	NewNode.Next = cur.Next
	cur.Next = NewNode
	this.Size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	// 首先判断索引是否合法
	if this == nil || index < 0 || index >= this.Size {
		return
	}
	cur := this.dummyHead
	// 遍历到掐一个节点进行删除
	// val(0) -> target(1) -> val(2)
	for i := 0; i < index; i++ {
		cur = cur.Next
	}
	cur.Next = cur.Next.Next
	this.Size--
}

// 打印链表
func (List *MyLinkedList) printLinkedList() {
	cur := List.dummyHead
	for cur.Next != nil {
		fmt.Printf("%d -> ", cur.Next.Val)
		cur = cur.Next
	}
	fmt.Println()
}

2. 循环链表

206.翻转链表

206. 反转链表 - 力扣（LeetCode）

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

1. 双指针法

每一次循环改变Head.Next 指向

func reverseList(head *ListNode) *ListNode {
    // 双指针写法
    var pre *ListNode

    cur := head

    for cur != nil {
        // 保存cur.Next的值
        next := cur.Next
        // pre <- cur
        cur.Next = pre

        // 移动cur和pre
        // 先移动pre,如果先移动了cur,cur后移之后,pre无法移动到了cur
        pre = cur
        cur = next
    }
    // 遍历结束的时候是cur指向nil,pre最后一个元素
    // 所以返回pre
    return pre
}

2. 递归法

24.两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即 , 只能进行节点交换 )

# 示例1: 
输入：head = [1,2,3,4]
输出：[2,1,4,3]

# 示例2：
输入：head = []
输出：[]

# 示例3:
输入：head = [1]
输出：[1]

循环条件 :
偶数 : cur.Next!=nil
奇数 : cur.Next.Next!=nil
必须要线判断偶数 , 再判断奇数for cur.Next!=nil && cur.Nex.Next.Next!=nil 奇数和偶数的情况

temp 临时值 :
如上图所示 , 需要保存两个临时值 , cur.Next 和cur.Next.Next.Next

stNode) *ListNode {
	dummy := &ListNode{

1. 三个节点互换


func swapPairs(head *Li
	    Next:head,
	}
	// 虚拟头结点
	cur := dummy
	for cur.Next != nil && cur.Next.Next != nil {
		// 第一步
		temp := cur.Next
		temp1 := cur.Next.Next.Next
		cur.Next = cur.Next.Next
		    
		// 第二步
		cur.Next.Next = temp
		
		// 第三部
		temp.Next = temp1
	
		cur = cur.Next.Next
	}
	  
	return dummy.Next
}

2. 递归方法

19.删除链表的倒数第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]

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 虚拟头结点
    dummyHead := &ListNode{
        Next:head,
    }
    // 定义快慢指针
    cur := head
    slow := dummyHead
    i := 1
    for cur != nil {
        cur = cur.Next
        if i > n {
            slow = slow.Next
        } 
        i++
    }
    // 修改指向的节点
    slow.Next = slow.Next.Next

    return dummyHead.Next
}

142.环形链表

142. 环形链表 II - 力扣（LeetCode）

给定一个链表的头节点 head , 返回链表开始入环的第一个节点。如果链表无环，则返回 nil 。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

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

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

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

目录CONTENT

算法学习-链表