Insert into a Cyclic Sorted List
update Jul 24, 2017 15:40
Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list. Return the inserted new node.
Notice
- 3->5->1 is a cyclic list, so 3 is next node of 1.
- 3->5->1 is same with 5->1->3
Example
Given a list, and insert a value 4:
3->5->1
Return 5->1->3->4
Basic Idea:
- 考虑当输入是null时的情况
- 当可以找到
curr <= target <= next时的情况 - target 比所有node值都大或者都小的情况
update 2017-11-21 01:59:08
这道题其实没有想象中的那么简单，而奇怪的是几个月前第一次刷这道题的时候还用一个错误解骗过了LintCode 的 OJ，导致一直没有发现问题。
问题在于：
首先我们考虑共有哪些情况 ：
- node is None；
- 我们找到了明确可以插入的位置：
curr.val <= x <= curr.next.val; - x 比当前 linked list 的所有元素都大，或者都小；
看到这里感觉还是没有问题的，和之前的分析也一样，但是关键就在于如何判断 x 比所有当前元素都大或者都小，此时需要分两种情况讨论：
给定 list 的元素不全都相同，例如 3,1,5；
这种情况我们可以通过判断
curr.val > curr.next.val来确定是否到达排序链表的 tail，然后分别判断 x 是否比 curr 和 curr.next 都大或者都小；给定 list 所有元素都相同，这种情况下就很容易出现死循环；
这种情况下，我们就需要记录一开始给定的 node，当出现
curr is node的时候，我们就知道我们一定已经循环了一整圈，并且不符合以上其他情况，那么一定是因为给定list所有元素都相同，无法判断出tail导致，此时可以直接插入 x；
综上所述
正确的做法其实是使用多个判断语句分情况讨论：
- 如果
curr is node，说明已经一圈结束，且所有元素都相同，可以插入； curr.val <= x <= curr.next.val，即恰好有位置插入；- 如果已经到 tail：
curr.val > curr.next.val，继续判断 首位两元素是否都大于或者都小于 x，如果是，则可以插入；
Java Code:
public class Solution {
/*
* @param node: a list node in the list
* @param x: An integer
* @return: the inserted new list node
*/
public ListNode insert(ListNode node, int x) {
ListNode target = new ListNode(x);
if (node == null) {
target.next = target;
return target;
}
ListNode curr = node;
while (true) {
if (curr.next == node ||
(curr.val <= x && curr.next.val >= x) ||
(curr.val > curr.next.val && (curr.val < x && curr.next.val < x ||
curr.val > x && curr.next.val > x))) {
target.next = curr.next;
curr.next = target;
return target;
}
curr = curr.next;
}
}
}
Python Code:
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
# @param {ListNode} node a list node in the list
# @param {int} x an integer
# @return {ListNode} the inserted new list node
def insert(self, node, x):
target = ListNode(x)
if node is None:
target.next = target
return target
curr = node
while True:
# *****************************************************
if (curr.next is node) or (curr.val <= x and curr.next.val >=x) or \
(curr.val > curr.next.val and \
(curr.val > x and curr.next.val > x or curr.val < x and curr.next.val < x)):
# *****************************************************
target.next = curr.next
curr.next = target
return target
curr = curr.next
return None
update 2017-11-21 14:18:45
总结
面对一道题的时候，应该在动手coding之前先想好所有的可能情况，有了通盘考虑之后再开始动手。
update 2018-6-30 22:27
Update
一种新的想法：
其实如果给定list的元素种类不是唯一的，就一定可以在一次循环中搞定，那么如果在循环结束（回到给定node）后没有搞定，则说明list中元素是唯一的，此时就可以直接插入；
所以在实现的时候，先用一层while循环处理list中元素不唯一的情况，如果在这次循环中没有解决，则直接插入target；
public class Solution {
public ListNode insert(ListNode node, int x) {
ListNode target = new ListNode(x);
target.next = target;
if (node == null) return target;
ListNode curr = node;
while (curr.next != node) {
if (curr.val <= x && curr.next.val >= x) {
target.next = curr.next;
curr.next = target;
return target;
} else if (curr.val > curr.next.val) {
// curr is min
if (x >= curr.val && x >= curr.next.val || x <= curr.val && x <= curr.next.val) {
target.next = curr.next;
curr.next = target;
return target;
}
}
curr = curr.next;
}
// 此时 curr.next == node, 循环一周后退出，说明所有元素都一样
target.next = curr.next;
curr.next = target;
return target;
}
}