Linked Lists

2022-02-14

鏈接清單 (Linked List)

鏈接清單是表示一系列節點(node)的資料結構。

doubly-linked-lists

與陣列不同，在鏈接清單中存取特定索引並非常數(constant)時間。
若要找到清單中的第K個元素，需要迭代K個元素。

建構鏈接清單

class Node
{
  public ?Node $next = null;
  public int $data;

  public function __construct(int $data)
  {
    $this->int = $data;
  }

  public function appendToTail(int $data)
  {
    $end = new Node($data);
    $n = $this;

    while ($n->next != null) {
      $n = $n->next;
    }

    $n->next = $end;
  }
}

此實作中沒有LinkedList資料結構。
我們透過第一個節點參考(reference)存取此鏈接清單。

以這種方式實作鏈接清單必須小心。
若有多個物件需要此鏈接清單的參考，而第一個節點改變了呢？

我們可以選擇實作包裝Node類別的LinkedList類別。
它只有一個成員變數：第一個Node。
這會大幅解決前述問題。

記得討論鏈接清單要知道是單向或雙向的。

從單向鏈接清單中刪除節點

對節點n找出前一個節點prev並將prev.next設定為n.next值。

若為雙向鏈接，還有將n.next.prev設定為n.prev值。

重點是檢查空指標與更新頭尾指標。

runner技巧

“runner” (或說是第二個指標) 技巧用於鏈接清單問題。
意思是同時以兩個指標迭代鏈接清單，其中一個領先另一個 (節點領先固定數量)。

遞迴問題

許多鏈接清單依靠遞迴解決。
但你應該要記住遞迴演算法至少需要$O(n)$空間，$n$是遞迴呼叫的深度。

所有遞迴演算法都可以用迭代實作，但會比較複雜。

面試問題

2.1 Remove Dups

Write code to remove duplicates from an unsorted linked list.

First Answer (hash table)

public static function removeDuplicated(Node $node)
{
  $hashTable = [];

  /**
   * @var ?Node $previousNode
   */
  $previousNode = null;

  while (!is_null($node)) {
      if (in_array($node->data, $hashTable)) {
          $previousNode->next = $node->next;
      } else {
          $hashTable[] = $node->data;
          $previousNode = $node;
      }

      $node = $node->getNext();
  }
}

Best Answer (two point)

public static function removeDuplicated(Node $node)
{
  $pointer1 = $node;

  while (!is_null($pointer1)) {
      $pointer2 = $pointer1;

      while (!is_null($pointer2->next)) {
          if ($pointer2->next->data == $pointer1->data) {
              $pointer2->next = $pointer2->next->next;
          } else {
              $pointer2 = $pointer2->next;
          }
      }

      $pointer1 = $pointer1->next;
  }
}

2.2 Return Kth to Last

Implement an algorithm to find the kth to last element of a singly linked list.

public static function find(Node $node, $k): ?Node
{
  $pointer1 = $node;
  $pointer2 = $node;

  for ($i = 0; $i < $k; $i++) {
      if (is_null($pointer1)) {
          return null;
      }

      $pointer1 = $pointer1->next;
  }

  while ($pointer1 != null) {
      $pointer1 = $pointer1->next;
      $pointer2 = $pointer2->next;
  }

  return $pointer2;
}

2.4 Partition

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the “right partition”; it does not need to appear between the left and right partitions.

[Example]

Input:
Output:
3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition= 5]
3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

public static function partition(Node $node, $x)
{
  $head = new Node();
  $headStart = $head;

  $tail = new Node();
  $tailStart = $tail;

  while (!is_null($node)) {
      $data = $node->data;

      if ($data < $x) {
          $head->next = new Node($data);
          $head = $head->next;
      } else {
          $tail->next = new Node($data);
          $tail = $tail->next;
      }

      $node = $node->next;
  }

  $head->next = $tailStart->next;

  return $headStart->next;
}

2.6 Palindrome

Implement a function to check if a linked list is a palindrome.

Solution #1 (Reverse and Compare)

public static function isPalindrome(?Node $node): bool
{
  $reversed = self::reverseAndClone($node);
  return self::isEqual($node, $reversed);
}

private static function reverseAndClone(Node $node): ?Node
{
  $head = null;

  while (!is_null($node)) {
    $n = new Node($node->data);
    $n->next = $head;

    $head = $n;
    $node = $node->next;
  }

  return $head;
}

private static function isEqual(?Node $node, ?Node $reversed): bool
{
  while (!is_null($node) && !is_null($reversed)) {
    if ($node->data != $reversed->data) {
      return false;
    }

    $node = $node->next;
    $reversed = $reversed->next;
  }

  return $node === $reversed;
}

ʕ •ᴥ•ʔ：程式碼可參考：CtCI-6th-php。

Algorithm