Ltd的算法大抄·链表I

// 迭代
func removeElements2(head *ListNode, val int) *ListNode {
	//虚拟节点，便于head和后面的统一操作
	dummyHead := &ListNode{Val: -1, Next: head}
	//使用临时节点进行迭代
	for tmp := dummyHead; tmp.Next != nil; {
		if tmp.Next.Val == val {
			//删除next节点
			tmp.Next = tmp.Next.Next
		} else {
			//继续迭代
			tmp = tmp.Next
		}
	}
	//最后返回的是头指针
	return dummyHead.Next
}

// 递归
func removeElements1(head *ListNode, val int) *ListNode {
	//表示到达链表尾部了
	if head == nil {
		return head
	}
	//递归，直到链表尾再递归返回，返回值是下一个节点本身或它的下一个节点（即当前节点的next.next）
	head.Next = removeElements1(head.Next, val)
	if head.Val == val {
		//返回当前节点的next，作为前一个节点的next，即意味着删除此节点
		return head.Next
	}
	//若不删除就返回当前节点
	return head
}

type MyLinkedList struct {
	dummyHead *ListNode
	size      int
}

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

func (m *MyLinkedList) Get(index int) int {
	//排除非法index
	if index < 0 || index >= m.size {
		return -1
	}
	tmp := m.dummyHead
	//索引为0的不是dummyHead,所以要到取等
	for i := 0; i <= index; i++ {
		tmp = tmp.Next
	}
	return tmp.Val
}

func (m *MyLinkedList) AddAtHead(val int) {
	m.AddAtIndex(0, val)
}

func (m *MyLinkedList) AddAtTail(val int) {
	m.AddAtIndex(m.size, val)
}

func (m *MyLinkedList) AddAtIndex(index int, val int) {
	if index > m.size {
		return
	}
	//索引小于0都视为在头节点之前加
	if index < 0 {
		index = 0
	}
	tmp := m.dummyHead
	//当索引为0时表示在头节点之前加入,即dummyHead之后,所以这里不取等
	for i := 0; i < index; i++ {
		tmp = tmp.Next
	}
	//新节点内容
	newNode := &ListNode{Val: val, Next: tmp.Next}
	tmp.Next = newNode
	m.size++
}

func (m *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= m.size {
		return
	}
	tmp := m.dummyHead
	for i := 0; i < index; i++ {
		tmp = tmp.Next
	}
	tmp.Next = tmp.Next.Next
	m.size--
}

// 迭代
func reverseList1(head *ListNode) *ListNode {
	var pre *ListNode = nil
	cur := head
	for cur != nil {
		//记录下一个
		next := cur.Next
		//反转
		cur.Next = pre
		//迭代
		pre = cur
		cur = next
	}
	//返回最后一个节点的指针,即反转后的head
	return pre
}

// 递归
func reverseList2(head *ListNode) *ListNode {
	//排除空链表或链尾的next
	if head == nil || head.Next == nil {
		return head
	}
	//返回递归之后的head节点
	last := reverseList2(head.Next)
	//反转，将head.next的下一个指向head
	head.Next.Next = head
	//当前指向nil,若是头节点就是nil了,若是中间节点会在递归后指向反转后的节点
	head.Next = nil
	//返回递归后的头节点
	return last
}

// 迭代
func swapPairs1(head *ListNode) *ListNode {
	dummyNode := &ListNode{Next: head}
	pre := dummyNode
	for pre.Next != nil && pre.Next.Next != nil {
		//分别记录好后面三个的位置
		next1 := pre.Next
		next2 := pre.Next.Next
		next3 := pre.Next.Next.Next

		//前序节点指向交换的第二个
		pre.Next = next2
		//第二个指向第一个
		next2.Next = next1
		//第一个指向第三个
		next1.Next = next3

		//移动两个节点的位置
		pre = pre.Next.Next
	}
	//返回头节点
	return dummyNode.Next
}

// 递归
func swapPairs2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	//交换的第二个节点，交换后是新的头节点
	newHead := head.Next
	//递归获取后面节点的头节点，传入是第三个节点
	head.Next = swapPairs2(newHead.Next)
	//交换，新的头节点的下一个是之前的头节点
	newHead.Next = head
	//返回新的头节点
	return newHead
}