Introduction to Algorithms, 2022-3
Week 7: Exercises

1. Adjacent Elements

We can use this class to represent a linked list node:

class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next

Write a function has_adjacent(n) that takes a pointer to the first Node in a linked list and returns True if any two adjacent elements in the list have the same value, otherwise False.

2. Prepend

You are given a class LinkedList with an attribute head that points to the head of a linked list of Node objects:

class LinkedList:
    def __init__(self, head):
        self.head = head

Write a method that prepends a value to a LinkedList.

3. Append

Write a method that appends a value to a LinkedList.

4. Delete First

Write a method that deletes the first node (if any) in a LinkedList.

5. Delete Last

Write a method that deletes the last node (if any) in a LinkedList.

6. Split a List

Write a function split() that takes a pointer to the the first Node in a linked list and splits the list into two linked lists of roughly equal size. Return a pair containing these lists. The elements in the returned lists may appear in any order.

7. Merge Lists

Write a function merge() that takes pointer to the first Nodes of two sorted lists and combines them into a single sorted list.

8. Linked List Merge Sort

Write a function merge_sort() that performs a merge sort on a linked list, returning a pointer to a sorted list. Do not allocate any new list nodes while sorting.