# O(nlogn) time O(n) space Python, converting to linked-list

• ``````class IntervalNode(object):
def __init__(self, interval):
self.interval = interval
self.next = None

class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
intervals = sorted(intervals, key=lambda x:x.start)
pre = None
ans = []
for i in xrange(0, len(intervals)):
interval = intervals[i]
node = IntervalNode(interval)
if pre:
pre.next = node
pre = node

while p:
if p.next and p.next.interval.start <= p.interval.end:
p.interval.end = max(p.next.interval.end, p.interval.end)
p.next = p.next.next
else:
p = p.next

while p:
ans.append(p.interval)
p = p.next
return ans
``````

• I'm curious why you chose to approach the problem this way. Was it just to practice building and using linked-lists?

• @acmiyaguchi Yes, just for fun!

• Awesome! Just a few nits. I think it looks more pythonic to use an iterator like the following

``````for interval in intervals:
...
``````

as opposed to using an index, especially if you aren't going to use the index for other things.

``````for i in xrange(0, len(intervals)):
interval = intervals[i]
``````

Also, most list-like objects have an internal sort method that does sorting in place instead of creating a new object. You could replace `sorted(...)` with `intervals.sort(key=lambda x: x.start)`.

Nice implementation of a linked list :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.