0086.partition-list

86. 分隔链表

题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解题思路

1. 双指针

具体解法

Golang

type ListNode struct {
	Val  int
	Next *ListNode
}

func partition(head *ListNode, x int) *ListNode {
	lessTop := &ListNode{}
	less := lessTop
	greaterTop := &ListNode{}
	greater := greaterTop
	for n := head; n != nil; n = n.Next {
		if n.Val < x {
			less.Next = n
			less = n
			continue
		}
		greater.Next = n
		greater = n
	}
	less.Next = greaterTop.Next
	greater.Next = nil
	return lessTop.Next
}