清风徐来
0%

Leetcode之反转链表

发表于 分类于

Reverse Linked List

No.206

Given the head of a singly linked list, reverse the list, and return the reversed list.

指针解法

1
2
3
4
5
6
7
8
9
10
11
12
func reverseList(head *ListNode) *ListNode {
  var prev *ListNode
	curr := head
	var last *ListNode
	for curr != nil {
		last = curr.Next
		curr.Next = prev
		prev = curr
		curr = last
	}
	return prev
}

递归解法

1
2
3
4
5
6
7
8
9
func reverseList(head *ListNode) *ListNode {
  if head == nil || head.Next == nil{
    return head
  }
  last := reverseList(head.Next)
  head.Next.Next = head
  head.Next = nil
  return last
}

反转链表前N个元素

在反转整个链表的基础上增加条件即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverseNth(head *ListNode, n int) *ListNode {
	var prev *ListNode = nil
	curr := head
	var last *ListNode
	for curr != nil && n > 0 {
		last = curr.Next
		curr.Next = prev
		prev = curr
		curr = last
		n--
	}
  // 连结
	head.Next = curr
	return prev
}