LeetCode-86

题目

86. 分隔链表

结果

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
	// small, large list with a dummy node
	var s, l ListNode
	sPtr, lPtr := &s, &l
	for p := head; p != nil; p = p.Next {
		if p.Val < x {
			sPtr.Next = &ListNode{Val: p.Val}
			sPtr = sPtr.Next
		} else {
			lPtr.Next = &ListNode{Val: p.Val}
			lPtr = lPtr.Next
		}
	}
	sPtr.Next = l.Next
	return s.Next
}

复杂度

时间复杂度：O（n）

空间复杂度：O（1）