题目
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
coding
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
// 使用两个虚拟指针节点
public ListNode partition(ListNode head, int x) {
ListNode dummySmall = new ListNode(-1);
ListNode dummyBig = new ListNode(-2);
ListNode smallCur = dummySmall;
ListNode bigCur = dummyBig;
ListNode cur = head;
while(cur != null){
if(cur.val < x){
smallCur.next = cur;
smallCur = smallCur.next;
}else{
bigCur.next = cur;
bigCur = bigCur.next;
}
cur = cur.next;
}
smallCur.next = dummyBig.next;
// 这里用的时同一个动态指针，所以是会成环的，要将他指向null
bigCur.next = null;
return dummySmall.next;
}
}
总结
- 总体思路
- 使用虚拟节点
- 当前题目使用两个虚拟节点，分别存储小的值和大的值
- 最后将两个节点连接起来
- 动态指针的位置需要按照如下图去理解
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96092.html
