单链表反转

题目来源

LeetCode 206. Reverse Linked List

精简解题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

type Node struct {
	Val  int
	Next *Node
}

func reverseList(h *Node) *Node {
	var cur *Node = h
	var prev *Node = nil
	for cur != nil {
		cur.Next, prev, cur = prev, cur, cur.Next
	}
	return prev
}

交互相邻节点

题目来源

LeetCode 24. Swap Nodes in Pairs

精简解题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func swapPairs(head *Node) *Node {
	list := &Node{Next: head}
	for prev, node := list, list.Next; node != nil; node = node.Next {
		if node.Next != nil {
			swapNode(prev, node, node.Next)
			prev = node
		}
	}
	return list.Next
}

func swapNode(prev, node, next *Node) {
	prev.Next = next
	node.Next = next.Next
	next.Next = node
}

检测是否有环

题目来源

LeetCode 141. Linked List Cycle

精简解题

思路:

  1. 快慢指针，有环必定相遇

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    func hasCycle(head *Node) bool {
	if head == nil || head.Next == nil {
		return false
	}
	quickP, slowP := head, head
	for quickP != nil {
		quickP = quickP.Next
		if quickP != nil {
			quickP = quickP.Next
		}
		slowP = slowP.Next
		if slowP == quickP {
			return true
		}
	}
	return false
}

给出环的起点位置

题目来源

LeetCode 142. Linked List Cycle 2

精简解题

思路:

  1. 快慢指针找到相遇结点

  2. 从链表头开始和慢指针同步走，直到相遇即环的入口

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    func detectCycle(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	slow, fast := head.Next, head.Next.Next
	for fast != nil && fast.Next != nil && slow != fast {
		slow, fast = slow.Next, fast.Next.Next
	}

	if slow != fast {
		return nil
	}

	for slow != head {
		slow, head = slow.Next, head.Next
	}
	return slow
}

k个节点翻转

题目来源

LeetCode 25. Reverse Nodes in K-Group

精简解题

思路:

  1. 计算链表长度，统计可以反转次数

  2. 累计k个结点，反转

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

    func reverseKGroup(head *ListNode, k int) *ListNode {
	l := head
	s := 0
	for l != nil {
		s++
		l = l.Next
	}
	ks := head
	ke := head
	retHead := ListNode{}
	retList := &retHead
	for count := int(s / k); count != 0; count-- {
		for i := 1; i < k; i++ {
			ke = ke.Next
		}
		ken := ke
		if ke != nil {
			ken = ke.Next
		}
		ke.Next = nil
		retList.Next = reverseList(ks)
		retList = ks
		ks = ken
		ke = ken
	}
	retList.Next = ke
	return retHead.Next
}

func reverseList(h *ListNode) *ListNode {
	var cur *ListNode = h
	var prev *ListNode = nil
	for cur != nil {
		cur.Next, prev, cur = prev, cur, cur.Next
	}
	return prev
}