清风徐来
0%

leetcode之删除链表的倒数第N个结点

发表于 分类于

Remove Nth Node From End of List

No.19

Given the head of a linked list, remove the nth node from the end of the list and return its head.

解题思路：需要移除倒数第N个节点，只需要找到n-1个节点x，将x.next指向x.next.next即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  t := &ListNode{0, head}
	p, c := t, t
	for n > 0 && p != nil {
		p = p.Next
		n--
	}
	if p == nil {
		return nil
	}
  // 这里需要注意 不能多走
	for p.Next != nil {
		p = p.Next
		c = c.Next
	}
	c.Next = c.Next.Next
	return t.Next
}

Linked List Cycle

No.141

Given head, the head of a linked list, determine if the linked list has a cycle in it.

1
2
3
4
5
6
7
8
9
10
11
func hasCycle(head *ListNode) bool {
    t1 := head
	for head != nil && head.Next != nil {
		head = head.Next.Next
		t1 = t1.Next
		if head == t1 {
			return true
		}
	}
	return false
}

Intersection of Two Linked Lists

No.160

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

还有另外两种解法1.找出长度差，然后让长链表从到终点与短链表长度一致处出发，循环判断 2.把链表连接起来，寻找环的起点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func getIntersectionNode(headA, headB *ListNode) *ListNode {
  h1, h2 := headA, headB
	for h1 != h2 {
		if h1 == nil {
			h1 = headB
		} else {
			h1 = h1.Next
		}

		if h2 == nil {
			h2 = headA
		} else {
			h2 = h2.Next
		}
	}
	return h1
}