lc面试准备：Partition List 1 题目 2 思路 3 代码 4 总结 5 参考
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
接口
ListNode partition(ListNode head, int x)
2 思路
给定一个x的值，小于x都放在大于等于x的前面，并且不改变链表之间node原始的相对位置。example中 4->3->5都是大于等3的数，这保持了他们原来的相对位置 。
思路1：使用链表最常用的双指针，一个指向当前小于x的最后一个元素，一个进行往前扫描。如果元素大于x，那么继续前进，否则，要把元素移到前面，并更新第一个指针。
思路2：
- new两个新链表，一个用来创建所有大于等于x的链表，一个用来创建所有小于x的链表。
- 遍历整个链表时，当当前node的val小于x时，接在小链表上，反之，接在大链表上。这样就保证了相对顺序没有改变，而仅仅对链表做了与x的比较判断。
- 最后，把小链表接在大链表。
复杂度
2种方法的时间和空间复杂度一样。
Time：O(n)
Space: O(1)
3 代码
1 // 思路2：dummy1 小于x的linkedlist; dummy2 大于等于x的linkedlist. 2 public ListNode partition(ListNode head, int x) { 3 ListNode dummy1 = new ListNode(-1); 4 ListNode dummy2 = new ListNode(-2); 5 ListNode t1 = dummy1, t2 = dummy2, pCur = head; 6 while (pCur != null) { 7 ListNode pTmp = pCur.next; 8 if (pCur.val < x) { 9 t1.next = pCur; 10 t1 = t1.next; 11 } else { 12 t2.next = pCur; 13 t2 = t2.next; 14 t2.next = null; 15 } 16 pCur = pTmp; 17 } 18 t1.next = dummy2.next; 19 return dummy1.next; 20 }
4 总结
- Two Pointer的思想
- 这是普通的链表操作，应该熟练掌握。
- 思路1实现细节要多些，用一个头结点、2个指针可以完成。
- 思路2实现简单明了。