【Leetcode】86. 分隔链表
【Leetcode】86. 分隔链表
Leetcode名企之路
发布于 2018-12-14 17:37:50
发布于 2018-12-14 17:37:50
双十一这波熬了两个通宵，有点伤，又开始A题，总结技术了。
题目
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5题解
链表的题目基本都是分三步走: 1.连过来。把想要的节点连到你需要的链表上 2.指针走。该节点处理完了,在原来的链表上要走一步. 3.断后路。当前链表不要和原来链表有连接 4.调状态。调整当前各指针的记录状态
其他部分仅仅是为了保存状态的。
链表的题目刷过100道之后我会做一个汇总,链表题目基本就是最简单的这三步,面到就是赚到。
java
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode preDummy = new ListNode(-1);
ListNode dummy = new ListNode(-1);
preDummy.next = dummy;
ListNode res = preDummy;
ListNode tail = dummy;
while (head != null) {
ListNode current = head;
if (head.val < x) {
//连过来
preDummy.next = current;
//指针走
head = head.next;
//断后路
current.next = dummy;
preDummy = preDummy.next;
} else {
//连过来
tail.next = current;
//指针走
head = head.next;
//断后路
current.next = null;
tail = tail.next;
}
}
preDummy.next = dummy.next;
return res.next;
}python
class Solution:
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
if head is None or head.next is None:
return head
preDummy = ListNode(-1)
dummy = ListNode(-1)
preDummy.next = dummy
res = preDummy
tail = dummy
while head is not None:
current = head
if head.val < x:
# 连过来
preDummy.next = current
# 指针走
head = head.next
# 断后路
current.next = dummy
# 调状态
preDummy = preDummy.next
else:
# 连过来
tail.next = current
# 指针走
head = head.next
# 断后路
current.next = None
# 调状态
tail = tail.next
preDummy.next = dummy.next
return res.next本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录