Skip to content

Linkedlist

Introduction

Each problem on the platform includes a direct solution, while others solely outline the approach within a function.

Solution

Source code in algorithms/linkedlists/palindromeLinkedList.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def palindromeLinkedList(self, head):
        """
        :type head : ListNode
        :rtype : bool
        """
        if not head or not head.next:
            return True
        list = []
        while head:
            list.append(head.val)
            head = head.next

        if list == list[::-1]:
            return True
        else:
            return False

palindromeLinkedList(head)

:type head : ListNode :rtype : bool

Source code in algorithms/linkedlists/palindromeLinkedList.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def palindromeLinkedList(self, head):
    """
    :type head : ListNode
    :rtype : bool
    """
    if not head or not head.next:
        return True
    list = []
    while head:
        list.append(head.val)
        head = head.next

    if list == list[::-1]:
        return True
    else:
        return False

Solution

Source code in algorithms/linkedlists/reversLinkedList.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def reverseLinkedList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev, curr = None, head     #two pointers   
        while curr:
            nxt = curr.next  #save the next node to iterate
            curr.next = prev
            prev = curr
            curr = nxt

        return prev     # return prev because the curr is Null

reverseLinkedList(head)

:type head: ListNode :rtype: ListNode

Source code in algorithms/linkedlists/reversLinkedList.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
def reverseLinkedList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    prev, curr = None, head     #two pointers   
    while curr:
        nxt = curr.next  #save the next node to iterate
        curr.next = prev
        prev = curr
        curr = nxt

    return prev     # return prev because the curr is Null

Solution

Source code in algorithms/linkedlists/removeNthNodefromEnd.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        ptr1 = dummy
        ptr2 = dummy

        for _ in range(n+1):
            ptr2 = ptr2.next

        while ptr2 is not None:
            ptr1 = ptr1.next
            ptr2 = ptr2.next

        ptr1.next = ptr1.next.next

        return dummy.next

removeNthFromEnd(head, n)

:type head: ListNode :type n: int :rtype: ListNode

Source code in algorithms/linkedlists/removeNthNodefromEnd.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def removeNthFromEnd(self, head, n):
    """
    :type head: ListNode
    :type n: int
    :rtype: ListNode
    """
    dummy = ListNode(0)
    dummy.next = head
    ptr1 = dummy
    ptr2 = dummy

    for _ in range(n+1):
        ptr2 = ptr2.next

    while ptr2 is not None:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    ptr1.next = ptr1.next.next

    return dummy.next

Solution

Bases: object

Source code in algorithms/linkedlists/mergeKsorted.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        if not lists:
            return None

        return self.merge(lists, 0 , len(lists)-1)

    def merge(self, lists, left, right):
        if left == right:
            return lists[left]

        mid = (left+right)//2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)

        return self.mergeTwoLists(l1, l2)

    def mergeTwoLists(self, l1, l2):
        if not l1:
            return l2
        elif not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

mergeKLists(lists)

:type lists: List[ListNode] :rtype: ListNode

Source code in algorithms/linkedlists/mergeKsorted.py 
30
31
32
33
34
35
36
37
38
39
def mergeKLists(self, lists):
    """
    :type lists: List[ListNode]
    :rtype: ListNode
    """

    if not lists:
        return None

    return self.merge(lists, 0 , len(lists)-1)

for more

still updating the site, for more hit