Algorithm (2): Linked Lists

Before we enter into “Question and Answer” model, we need to know how to use LinkedList in Scala. In Scala, it already provides LinkedList collection directly. by “import scala.collection.mutable.LinkedList”.

import scala.collection.mutable.LinkedList
val temp = new LinkedList[String]
val temp1 = temp append LinkedList("abc", "efg")
println(temp1)
// output: LinkedList("abc", "efg")
// Note: now temp is still LinkedList()

2.1 Write code to remove duplicates from an unsorted linked list. Follow up: how would you solve this problem if a temporary buffer is not allowed?

import scala.collection.mutable.LinkedList
import scala.collection.mutable.HashMap
def removeDuplicate(data: LinkedList[String]): LinkedList[String] = {
  val record = new HashMap[String, Int]
  var dataTemp = data
  var previous: LinkedList[String] = LinkedList()
  while (dataTemp != LinkedList()) {
    if (record.isDefinedAt(dataTemp.elem)) {
      previous.next = dataTemp.next
    } else {
      record.put(dataTemp.elem, 1)
      previous = dataTemp
    }
    dataTemp = dataTemp.next
  }
  data
}

Here we use hashmap to store each element and its appearance time. We use record.isDefinedAt to check whether this key exists or not and use record.put to add new pair to map.

For linkedlist, we use dataTemp.elem to get current data and dataTemp.next to its tail: linkedlist. Also in Scala, you can directly use “dataTemp.distinct” to remove duplicates.

2.2 Implement an algorithm to find last n elements of a singly linked list

def getNth(data: LinkedList[String], n: Int): LinkedList[String] = {
  var length = 0
  var dataTemp = data
  while (dataTemp != LinkedList()) {
    length += 1
    dataTemp = dataTemp.next
  }
  if (n == length) {
    data
  } else if (n > length) {
    LinkedList()
  } else {
    dataTemp = data 
    var count = 1
    while (dataTemp != LinkedList() && count + n != length) {
      count += 1
      dataTemp = dataTemp.next
    }
    dataTemp.next
  }
}

Note: I change the question content which is different with the book.

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.

Example:

Input: the node ‘c’ from the linked list a->b->c->d->e

Result: nothing is returned, but the new linked list looks like a->b->d->e

def removeMiddle(data: LinkedList[String], middle: String) = {
  var dataTemp = data
  var returnData = data
  var previous = data
  while(dataTemp.next.elem != middle) {
    previous = dataTemp.next
    dataTemp = dataTemp.next
  }
  previous.next = dataTemp.next.next
  println(returnData)
}

2.4 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Example:

Input: (3->1->5), (5->9->2)

Output: 8->0->8

This question looks like to implement an add function for linked list.

def addLinkedList(first: LinkedList[Int], second: LinkedList[Int]): LinkedList[Int] = {
  var sum = LinkedList[Int]()
  var firstTemp = first
  var secondTemp = second
  var flag = 0
  while (firstTemp != LinkedList() && secondTemp != LinkedList()) {
    val temp = firstTemp.elem + secondTemp.elem + flag
    sum = sum append LinkedList(temp % 10)
    flag = if (temp <= 9) 0 else 1
    firstTemp = firstTemp.next
    secondTemp = secondTemp.next
  }
  if (firstTemp == LinkedList()) {
    while (secondTemp != LinkedList()) {
      val temp = secondTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      secondTemp = secondTemp.next
    }
  } 
  if (secondTemp == LinkedList()){
    while (firstTemp != LinkedList()) {
      val temp = firstTemp.elem + flag
      sum = sum append LinkedList(temp % 10)
      flag = if (temp <= 9) 0 else 1
      firstTemp = firstTemp.next
    }
  }
  if (flag != 0) {
    sum = sum append LinkedList(flag)
  }
  sum
}

2.5 Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.

Definition:

Circular linked list: A(corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

example:

Input: A->B->C->D->E->C [the same C as earlier]

Output: C

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s