链表

[yifanzheng]

链表

链表是通过“指针”将一组零散的内存块串联起来使用，其中内存块称为链表的“结点”。链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。但是正因为存储空间不连续，你无法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。

处理链表时需要检查的几个点：

• 链表是否为空
• 链表是否只包含一个结点
• 链表是否只包含两个结点
• 注意头结点和尾结点的处理逻辑

算法题练习

• 实现单链表
• 反转链表
• 回文链表
• 合并两个有序链表（简单）
• 删除链表中的节点（简单）
• 删除链表的倒数第 N 个结点（中等）
• 链表的中间结点（简单）
• 环形链表（简单）
• 合并 K 个有序链表（困难）
• 环形链表II（中等）
• 相交链表（简单）
• 反转链表II（中等）

[yifanzheng]

实现单链表

/**
 * 单链表，支持插入、删除、查找操作；
 * 链表中存储得是int类型得数据；
 *
 * @author star
 */
public class LinkeList {

    private Node head = null;

    public void addFirst(int value) {
        Node newNode = new Node(value, null);
        if (head == null) {
            head = newNode;
            return;
        }
        newNode.next = head;
        head = newNode;

    }

    public void addLast(int value) {
        Node newNode = new Node(value, null);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    public Node getByIndex(int index) {
        Node temp = head;
        int pos = 0;
        while (temp != null && pos != index) {
            temp = temp.next;
            pos++;
        }

        return temp;
    }

    public void deleteByIndex(int index) {
        if (head == null) {
            return;
        }
        Node temp = head;
        int pos = 0;
        while (temp != null && pos != index) {
            temp = temp.next;
            pos++;
        }
        // 没有找到指定索引的节点
        if (temp == null) {
            return;
        }
        // 找到节点，并且就是头节点
        if (temp.next == null) {
            head = head.next;
        } else {
            temp.next = temp.next.next;
        }
    }

    private void deleteByValue(int value) {
        if (head != null && head.data == value) {
            head = head.next;
            return;
        }
        // 重复删除指定 value 的节点
        Node temp = head;
        while (temp != null) {

            if (temp.next != null && temp.next.data == value) {
                temp.next = temp.next.next;
                continue;
            }
            temp = temp.next;
        }
    }

    public void printAll() {
        Node temp = head;
        StringBuilder builder = new StringBuilder();
        builder.append("[");
        while (temp != null) {
            builder.append(temp.getData());
            temp = temp.next;
            if (temp != null) {
                builder.append(",");
            }
        }
        builder.append("]");
        System.out.println(builder);
    }


    public class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }
}

[yifanzheng]

反转链表

LeetCode 地址：206.反转链表

题解

迭代

public ListNode reverseList(Node head) {
    Node prev = null;
    Node curr = head; 
    while (curr != null) {
       Node temp = curr.next;
       curr.next = prev;
       prev = curr;
       curr = temp;
    }
    return prev;
}

[yifanzheng]

回文链表

LeetCode 地址：234. 回文链表

题解

方法一：双指针

public boolean isPalindromeWithTwoPoint(Node head) {
     if (head == null) {
          return true;
      }
      // 1. 将链表转换成数组
      List<Integer> values = new ArrayList<>();
      ListNode temp = head;
      while (temp != null) {
          values.add(temp.val);
          temp = temp.next;
      }
      // 2. 定义首尾指针，两指针同时相向移动，并比较值是否相等
      int front = 0;
      int back = values.size() - 1;
      while (front < back) {
          // 移动过程中只要发现有不等的值，就返回 false
          if (!Objects.equals(values.get(front), values.get(back))) {
              return false;
          }
          front++;
          back--;
      }
      return true;
 }

方法二：快慢指针

public boolean isPalindromeWithFastSlowPoint(Node head) {
      if (head == null) {
          return true;
      }
      // 1. 定义快慢指针
      Node fast = head;
      Node slow = head;
      // 2. 找到中间节点。
      // 慢指针走一步，快指针走两步，当快指针到底尾部时，慢指针刚好在中间
      while (fast.next != null && fast.next.next != null) {
          fast = fast.next.next;
          slow = slow.next;
      }
      // 3. 反转后半部分节点。这里需要注意链表是奇数和偶数
      Node backHalfHead = reverseList(slow.next);
      Node frontHalfHead = head;
      // 4. 双指针进行比较
      while (backHalfHead != null) {
          if (!Objects.equals(backHalfHead.val, frontHalfHead.val)) {
             return false;
          }
          backHalfHead = backHalfHead.next;
          frontHalfHead = frontHalfHead.next;
      }

      return true;

}

public ListNode reverseList(Node head) {
    Node prev = null;
    Node curr = head; 
    while (curr != null) {
       Node temp = curr.next;
       curr.next = prev;
       prev = curr;
       curr = temp;
    }
    return prev;
}

[yifanzheng]

合并两个有序链表

LeetCode 地址：21. 合并两个有序链表

题解

方法一：循环迭代

同时从头遍历两个链表，在遍历过程中比较两个节点的大小，较小的节点放在新链表的前面并且将所在链表的指针向前移动，直到链表到达末尾。

public Node mergeTwoLists(Node list1, Node list2) {
        // 初始化一个虚拟节点
        Node newList = new Node(-1, null);

        Node temp1 = list1;
        Node temp2 = list2;
        // 临时指针
        Node preHead = newList;
        while (temp1 != null && temp2 != null) {
            if (temp1.val >= temp2.val) {
                preHead.next = temp2;
                temp2 = temp2.next;
            } else {
                preHead.next = temp1;
                temp1 = temp1.next;
            }
            // 指针向前移动
            preHead = preHead.next;
        }
        preHead.next = temp1 == null ? temp2 : temp1;
        return newList.next;
}

代码中用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。如果不使用虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

[yifanzheng]

删除链表中的节点

LeetCode 地址：237.删除链表中的节点

题解

只能直接访问要被删除的节点 ，数据保证需要删除的节点不是末尾节点 。

由于输入的是被删除节点，要删除此节点，可以将此节点的值修改成它的 next 节点的值，达到删除自己的效果。

public  void deleteNode(Node deleteNode) {
     deleteNode.val = deleteNode.next.val;
     deleteNode.next = deleteNode.next.next;
}

[yifanzheng]

删除链表的倒数第 N 个结点

LeetCode 地址：19.删除链表的倒数第 N 个结点

题解

方法一：计算出链表长度再进行删除

先计算出链表的长度 L，然后从头再对链表进行一次遍历，当遍历到第 L- N + 1 结点时，便是要删除的节点。但为了方便删除目标结点，可以从哑结点开始遍历 L- N + 1 个节点，当遍历到第 L- N + 1 结点时，它的下一个结点就是需要删除的结点。

public Node removeNthFromEnd(Node head, int n) {
    // 计算链表的长度
    int length = 0;
    Node temp = head;
    while (temp != null) {
        temp = temp.next;
        length++;
    }
    // 设置一个哑结点（哨兵），方便进行结点删除
    Node node = new Node(-1, head);
    Node temp1 = node;
    for (int i = 0; i < length - n; i++) {
        temp1 = temp1.next;
    }
    temp1.next = temp1.next.next;
    return node.next;
}

方法二：双指针

快指针先向前移动 N 步，慢指针再开始移动。快指针移动一步，慢指针也移动一步，当快指针移动到链表末尾时，慢指针刚好在链表倒数第 N 个位置。但为了方便删除目标结点，慢指针可以从哑结点（哨兵结点）开始向前移动。

public Node removeNthFromEnd(Node head, int n) {
    // 定义一个哑结点
    Node node = new Node(-1, head);
    Node fastNode = head;
    Node slowNode = node;
    // 快指针先向前移动 n 步
    for (int i = 0; i < n; i++) {
        fastNode = fastNode.next;
    }
    while (fastNode != null) {
        fastNode = fastNode.next;
        slowNode = slowNode.next;
    }
    slowNode.next = slowNode.next.next;
    return node.next;
}

[yifanzheng]

链表的中间结点

LeetCode 地址：876.链表的中间结点

题解

方法一：计算链表长度，单指针遍历

先计算出链表的长度 L，然后使用指针移动到链表第 (L/2) 结点处，便是链表中间位置。

public Node middleNode(Node head) {
    int len = 0;
    Node temp = head;
    while (temp != null) {
        temp = temp.next;
        len++;
    }
    Node cur = head;
    int p = 0;
    while (p < len / 2) {
        cur = cur.next;
        p++;
    }
    return cur;
}

方法二：快慢指针

使用快慢两个指针遍历链表，慢指针向前移动一步，快指针向前移动两步。当快指针走到链表末尾时，慢指针便位于链表中间位置。

public Node middleNode(Node head) {
    Node fastPoint = head;
    Node slowPoint = head;

    while (fastPoint != null && fastPoint.next != null) {
        fastPoint = fastPoint.next.next;
        slowPoint = slowPoint.next;
    }
    return slowPoint;
}

[yifanzheng]

环形链表

LeetCode 地址：141.环形链表

题解

方法一：哈希表

遍历链表，每次遍历到一个结点，判断此结点是否被访问过。

public boolean hasCycle(Node head) {
    Set<Node> seen = new HashSet<>();
    while (head != null) {
        if (!seen.add(head)) {
            return true;
        }
        head = head.next;
    }
    return false;
}

方法二：快慢指针

快慢指针都从 head 位置出发，慢指针每次移动一步，而快指针每次移动两步。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表；否则快指针将到达链表尾部，该链表不为环形链表。

public boolean hasCycle(Node head) {
    Node fastPoint = head;
    Node slowPoint = head;
    do {
        if (fastPoint == null || fastPoint.next == null) {
            return false;
        }
        slowPoint = slowPoint.next;
        fastPoint = fastPoint.next.next;
    } while (fastPoint != slowPoint);

    return true;
}

[yifanzheng]

合并K个升序链表

LeetCode 地址：23. 合并K个升序链表

题解

思路：将 K 个链表中的第一个节点依次放入优先级队列（小顶堆）中，然后选择最小的一个节点放入新的链表中，并且将它从队列中删除。然后再取此节点所在链表的下一个节点放入队列中，进行上述步骤，依次类推。

 public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap =
                new PriorityQueue<>(lists.length, Comparator.comparingInt(a -> a.val));
        // 将所有链表的头节点放入小顶堆中
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.add(node);
            }
        }
        // 初始化一个虚拟节点
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (!minHeap.isEmpty()) {
            ListNode min = minHeap.poll();
            temp.next = min;
            if (min.next != null) {
                minHeap.add(min.next);
            }
            // 指针前移
            temp = temp.next;
        }

        return dummy.next;
    }

[yifanzheng]

环形链表 II

LeetCode 地址：142. 环形链表 II

题解

方法一：哈希表

使用哈希表是最简单的方式，每次访问节点时，先判断哈希表中是否存在相同节点，如果存在，就返回；如果不存在，就将节点放入哈希表中，继续进行下一个节点的访问。

public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        Set<ListNode> seen = new HashSet<>();
        ListNode temp = head;
        while (temp != null) {
            if (!seen.add(temp)) {
               return temp;
            }
            temp = temp.next;
        }

        return null;
    }

方法二：快慢指针

 public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // 进行环检测
        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);
        // 如果是环形链表，则开始寻找环的起点
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

[yifanzheng]

相交链表

LeetCode 地址：160. 相交链表

题解

方法一：哈希表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      if (headA == null || headB == null) {
            return null;
        }
        // 将 A 链表放入 HashSet 中
        Set<ListNode> seen = new HashSet<>();
        ListNode temp = headA;
        while (temp != null) {
            seen.add(temp);
            temp = temp.next;
        }
        // 遍历 B 链表，判断 HashSet 中是否存在相同节点
        ListNode tempB = headB;
        while (tempB != null) {
            if (seen.contains(tempB)) {
                return tempB;
            }
            tempB = tempB.next;
        }
        return null;
    }

方法二：双指针

思路：将链表 A 和 链表 B 进行拼接，当 pA 指针遍历完 A 链表后，又去遍历 B 链表；当 pB 指针遍历完 B 链表后，又去遍历 A 链表。这样在逻辑上相当于两个链表连在了一起。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            if (tempA == null) {
               tempA = headB;
            } else {
                tempA = tempA.next;
            }
            if (tempB == null) {
                tempB = headA;
            } else {
                tempB = tempB.next;
            }
        }
        return tempA;
 }

[yifanzheng]

反转链表 II

LeetCode 地址：92. 反转链表 II

题解

方法一：双指针（迭代）

思路：先找到 left 位置的节点，再找到 right 位置的节点，然后将 left 和 right 之间的链表进行反转，最后又将反转后的链表接回原链表、

public ListNode reverseBetween(ListNode head, int left, int right) {
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      // 找到 left 位置的前一个节点
      ListNode leftPreNode = dummy;
      for (int i = 0; i < left - 1; i++) {
          leftPreNode = leftPreNode.next;
      }
      // 找到 right 位置的节点
     ListNode rightNode = leftPreNode;
      for (int i = 0; i < right - left + 1; i++) {
          rightNode = rightNode.next;
      }
      // 截取子链表
      ListNode leftNode = leftPreNode.next;
      ListNode rightNextNode = rightNode.next;
      // 截断链表
      leftPreNode.next = null;
      rightNode.next = null;

      // 反转链表
      reverse(leftNode);
      // 将反转后的链表连接起来
      leftPreNode.next = rightNode;
      // 由于反转了，所以 leftNode 跑到后面去了
      leftNode.next = rightNextNode;
      return dummy.next;
}

private void reverse(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
}

方法二：双指针（头插法）

思路：找到 left 位置的节点，然后使用头插法进行节点反转，直到反转到 right 位置。

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 找到 left 位置的前一个节点
    ListNode pre = dummy;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    ListNode p = pre.next;
    for (int i = 0; i < right - left; i++) {
      ListNode nextNode = p.next;
      p.next = nextNode.next;
      nextNode.next = pre.next;
      pre.next = nextNode;
    }

    return dummy.next;
}