数据结构与算法

前面，我们实现了链表的 反转 操作，本篇来聊聊，如何检测单链表中的环。链表环检测Leetcode 141: Linked List Cycle有两种方法来解决这个问题：使用Hashing思路定义一个Map，当循环遍历Linked List时，依次将Node放入Map中，等到循环到下一轮时，检查Node是否存在于Map中，若存在则表示有环存在。实现/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } /public class Solution { public boolean hasCycle(ListNode head) { Map map = new IdentityHashMap(); for(ListNode x = head; x != null;){ if(map.containsKey(x)){ return true; } map.put(x, null); x = x.next; } return false; }}Floyd判圈算法Floyd判圈算法如果有限状态机、迭代函数或者链表上存在环，那么在某个环上以不同速度前进的2个指针)必定会在某个时刻相遇。同时显然地，如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇，那么可以判定存在一个环，且可以求出2者相遇处所在的环的起点与长度。从Linked List的Head节点出发，我们定义两个移动指针，一个的移动速度为每次前进一个节点，另一个每次前进两个节点。然后判断这两个指针移动后的结果是否相等。代码/* * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ return true; } } return false; }}这两种方式的时间复杂度均为O(n)，空间复杂度均为O(1).参考资料https://www.geeksforgeeks.org…https://marcin-chwedczuk.gith…Floyd判圈算法《数据结构与算法之美》 ...

前面我们实现了几种常见的 链表 ，接下来，我们来聊聊如何实现 单链表 的反转？链表反转Leetcode 206: Reverse Linked List示例：Input: 1->2->3->4->5->NULLOutput: 5->4->3->2->1->NULLInput: NULLOutput: NULL我们可以通过循环遍历和递归这两种方式来实现链表的反转。遍历思路定义三个指针，分别为prev、curr、next，然后遍历所有node结点，并移动这三个指针，改变curr结点的next指向，指向prev结点，实现linkedList的反转。代码实现/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } /class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; ListNode next = null; while(curr != null){ next = curr.next; curr.next = prev; prev = curr; curr = next; } head = prev; return head; }}源码递归其实递归的实现方式和前面循环的方式非常相似，前者是通过循环来移动指针，后者是通过递归来移动指针。定义一个递归接口，传入curr与prev节点作为参数，内部再将curr的作为下次递归调用的prev入参，curr.next 作为下次递归调用的curr入参。代码实现/* * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList(ListNode head){ return reverseRecursively(head, null); } public ListNode reverseRecursively(ListNode curr, ListNode prev) { if(curr == null){ return null; } if(curr.next == null){ ListNode head = curr; curr.next = prev; return head; } ListNode next1 = curr.next; curr.next = prev; ListNode head = reverseRecursively(next1, curr); return head; }}源码这两种方式的时间复杂度均为O(n)，空间复杂度均为O(1)。参考资料《数据结构与算法之美》 ...

原文链接: https://wangwei.one/posts/jav…链表定义逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。<!–more–>由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。这种结构成为 “单向链表”。在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。当双向链表的头部和尾部相互指向时，就构成了双向循环链表。单向链表单向链表在插入元素、删除元素时，需要获取前驱元素，需要从head开始遍历，时间复杂度为O(n)。根据index查询对应元素，也需要从head开始遍历，时间复杂度为O(n)。代码实现package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/** * Single Linked List * * @author https://wangwei.one * @date 2018/12/25 /public class SingleLinkedList<T> implements IList<T> { /* * size / private int size = 0; /* * head node / private Node<T> head; /* * tail node / private Node<T> tail; /* * add element * * @param element * @return / @Override public boolean add(T element) { return addLast(element); } /* * add element at index * * @param index * @param element * @return / @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } if (index == size) { return add(element); } else { return addBefore(index, element); } } /* * Add Last element * * @param element * @return / private boolean addLast(T element) { Node<T> last = tail; Node<T> newNode = new Node<>(null, element); tail = newNode; // if linked list is empty if (last == null) { head = newNode; } else { last.next = newNode; } size++; return true; } /* * add element before certain element * * @param index * @param element * @return / private boolean addBefore(int index, T element) { checkPositionIndex(index); // prev node Node<T> prev = null; Node<T> x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // current node Node<T> current = x; // new node Node<T> newNode = new Node<>(current, element); // if current node is head if (prev == null) { head = newNode; } else { prev.next = newNode; } size++; return true; } /* * remove element * * @param element * @return / @Override public boolean remove(T element) { Node<T> prev = null; Node<T> x = head; if (element == null) { while (x != null && x.element != null) { prev = x; x = x.next; } } else { while (x != null && !x.element.equals(element)) { prev = x; x = x.next; } } // if this linked is null OR don’t find element if (x == null) { return false; } Node<T> next = x.next; // if delete node is head if (prev == null) { head = next; } else { prev.next = next; } // if delete node is tail if (next == null) { tail = prev; } // for GC x.element = null; x = null; size–; return true; } /* * remove element by index * * @param index * @return / @Override public T remove(int index) { checkPositionIndex(index); Node<T> prev = null; Node<T> x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // if linked is empty if (x == null) { return null; } Node<T> next = x.next; // if delete node is head if (prev == null) { head = next; } else { prev.next = next; } // if delete node is tail if (next == null) { tail = prev; } size–; return x.element; } /* * set element by index * * @param index * @param element * @return old element / @Override public T set(int index, T element) { checkPositionIndex(index); Node<T> node = node(index); T oldElement = node.element; node.element = element; return oldElement; } /* * get element by index * * @param index * @return / @Override public T get(int index) { Node<T> node = node(index); return node == null ? null : node.element; } /* * get element by index * * @param index * @return / private Node<T> node(int index) { checkPositionIndex(index); Node<T> x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } /* * check index * * @param index / private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } } /* * clear list / @Override public void clear() { for (Node<T> x = head; x != null; ) { Node<T> next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /* * contain certain element * * @param element / @Override public boolean contains(T element) { if (element == null) { for (Node<T> x = head; x != null; x = x.next) { if (x.element == null) { return true; } } } else { for (Node<T> x = head; x != null; x = x.next) { if (x.element.equals(element)) { return true; } } } return false; } /* * get list size * * @return / @Override public int size() { return size; } /* * Linked List Node * * @param <T> / private class Node<T> { private Node<T> next; private T element; public Node(Node<T> next, T element) { this.next = next; this.element = element; } }}源代码双向链表相比于单向链表，双向链表多了一个前驱指针，在查找前驱节点时，时间复杂度降低为了O(1)。通过index查询，删除某个node节点，时间复杂度都降为了O(1)。代码如下：代码实现package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/* * Doubly Linked List * * @param <T> * @author https://wangwei.one * @date 2018/04/28 /public class DoublyLinkedList<T> implements IList<T> { /* * size / private int size = 0; /* * head element / private Node<T> head = null; /* * tail element / private Node<T> tail = null; /* * add element * * @param element * @return / @Override public boolean add(T element) { return addLast(element); } /* * add element at index * * @param index * @param element * @return / @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } if (index == size) { return add(element); } else { return addBefore(element, node(index)); } } /* * Add Last element * * @param element * @return / private boolean addLast(T element) { final Node<T> last = tail; Node<T> newNode = new Node<>(last, element, null); tail = newNode; if (last == null) { head = newNode; } else { last.next = newNode; } size++; return true; } /* * add element before certain element * * @param element * @param target * @return / private boolean addBefore(T element, Node<T> target) { Node<T> prev = target.prev; Node<T> newNode = new Node<>(prev, element, target); target.prev = newNode; if (prev == null) { head = newNode; } else { prev.next = newNode; } size++; return true; } /* * remove node by element * * @param element * @return / @Override public boolean remove(T element) { if (element == null) { for (Node<T> x = head; x != null; x = x.next) { if (x.element == null) { unlink(x); return true; } } } else { for (Node<T> x = head; x != null; x = x.next) { if (element.equals(x.element)) { unlink(x); return true; } } } return false; } /* * remove node by index * * @param index * @return / @Override public T remove(int index) { return unlink(node(index)); } /* * get element by index * * @param index * @return / private Node<T> node(int index) { checkPositionIndex(index); if (index < (size >> 1)) { Node<T> x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node<T> x = tail; for (int i = size - 1; i > index; i–) { x = x.prev; } return x; } } /* * unlink node * * @param node / private T unlink(Node<T> node) { final T element = node.element; final Node<T> prev = node.prev; final Node<T> next = node.next; // if unlink is head if (prev == null) { head = next; } else { prev.next = next; // clear prev node.prev = null; } // if unlink is tail if (next == null) { tail = prev; } else { next.prev = prev; node.next = null; } node.element = null; size–; return element; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } } /* * set element by index * * @param index * @param element * @return / @Override public T set(int index, T element) { checkPositionIndex(index); Node<T> oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /* * get element by index * * @param index * @return / @Override public T get(int index) { Node<T> node = node(index); return node == null ? null : node.element; } /* * clear list / @Override public void clear() { for (Node<T> x = head; x != null; ) { Node<T> next = x.next; x.element = null; x.next = null; x.prev = null; x = next; } head = tail = null; size = 0; } /* * contain certain element * * @param element / @Override public boolean contains(T element) { if (element == null) { for (Node<T> x = head; x != null; x = x.next) { if (x.element == null) { return true; } } } else { for (Node<T> x = head; x != null; x = x.next) { if (element.equals(x.element)) { return true; } } } return false; } /* * get list size * * @return / @Override public int size() { return size; } /* * node * * @param <T> / private class Node<T> { private T element; private Node<T> prev; private Node<T> next; public Node(Node<T> prev, T element, Node<T> next) { this.element = element; this.prev = prev; this.next = next; } }}源代码单向循环链表与单向链表一样，在寻找前驱节点时，需要遍历整个链表，时间复杂度为O(n).在第一次添加元素时，特别注意，head与tail为同一节点，并且需要自指向。package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/* * Singly Circular Linked List * * @param <T> * @author https://wangwei.one * @date 2018/05/03 /public class SinglyCircularLinkedList<T> implements IList<T> { /* * size / private int size = 0; /* * head node / private Node<T> head = null; /* * tail node / private Node<T> tail = null; /* * add element * * @param element * @return / @Override public boolean add(T element) { return addLast(element); } /* * add element at index * * @param index * @param element * @return / @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } if (index == size) { return add(element); } else { return addBefore(index, element); } } /* * Add Last element * * @param element * @return / private boolean addLast(T element) { final Node<T> last = tail; Node<T> newElement = new Node<>(element, head); tail = newElement; if (last == null) { head = newElement; // we need linked itself when add an element first tail.next = head; } else { last.next = newElement; } size++; return true; } /* * add element before certain element * * @param element * @param element * @return / private boolean addBefore(int index, T element) { checkPositionIndex(index); // prev node, start with tail Node<T> prev = tail; Node<T> x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // current node Node<T> current = x; // new node Node<T> newNode = new Node<>(element, current); if (index == 0) { head = newNode; } prev.next = newNode; size++; return true; } /* * remove node by element * * @param element * @return / @Override public boolean remove(T element) { // start with tail Node<T> prev = tail; // start with head Node<T> x = head; // start with index -1 int prevIndex = -1; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { break; } if (element != null && element.equals(x.element)) { break; } prev = x; x = x.next; prevIndex = i; } // if this linked list is empty if (x == null) { return false; } // if don’t match element if (prevIndex == size - 1) { return false; } Node<T> next = x.next; // if delete node is head if (prevIndex == -1) { head = next; } // if delete node is tail if (prevIndex == size - 2) { tail = prev; } prev.next = next; size–; if (size == 0) { head = tail = null; } // for GC x = null; return true; } /* * remove element by index * * @param index * @return / @Override public T remove(int index) { checkPositionIndex(index); Node<T> prev = tail; Node<T> x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // if linked is empty if (x == null) { return null; } Node<T> next = x.next; // if delete node is head if (index == 0) { head = next; } // if delete node is tail if (index == size - 1) { tail = prev; } prev.next = next; size–; if (size == 0) { head = tail = null; } return x.element; } /* * get element by index * * @param index * @return / private Node<T> node(int index) { checkPositionIndex(index); Node<T> x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } } /* * set element by index * * @param index * @param element * @return / @Override public T set(int index, T element) { checkPositionIndex(index); Node<T> oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /* * get element by index * * @param index * @return / @Override public T get(int index) { return node(index).element; } /* * clear list element / @Override public void clear() { for (Node<T> x = head; x != null; ) { Node<T> next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /* * contain certain element * * @param element / @Override public boolean contains(T element) { if (head == null) { return false; } Node<T> x = head; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { return true; } if (element != null && element.equals(x.element)) { return true; } x = x.next; } return false; } /* * get list size * * @return / @Override public int size() { return size; } /* * Node * * @param <T> / private class Node<T> { private T element; private Node<T> next; public Node(T element, Node<T> next) { this.element = element; this.next = next; } }}源代码双向循环链表双向循环链表相比单向循环链表，降低了查找前驱节点的复杂度，时间复杂度为O(1).同样第一次添加元素时，head与tail为同一元素，需要自指向。package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/* * Doubly circular linked list * * @author https://wangwei.one * @date 2018/12/21 /public class DoublyCircularLinkedList<T> implements IList<T> { /* * size / private int size; /* * head node / private Node<T> head; /* * tail node / private Node<T> tail; /* * add element * * @param element * @return / @Override public boolean add(T element) { return addLast(element); } /* * add element at index * * @param index * @param element * @return / @Override public boolean add(int index, T element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } if (index == size) { return add(element); } else { return addBefore(index, element); } } /* * Add last element * * @param element * @return / private boolean addLast(T element) { Node<T> last = tail; Node<T> newNode = new Node<>(element, last, head); tail = newNode; // add element at first if (last == null) { head = newNode; tail.next = head; } else { last.next = newNode; } head.prev = tail; size++; return true; } /* * add element before certain element * * @param index * @param element * @return / private boolean addBefore(int index, T element) { Node<T> target = node(index); Node<T> prev = target.prev; Node<T> newNode = new Node<>(element, prev, target); prev.next = newNode; target.prev = newNode; if (index == 0) { head = newNode; } size++; return true; } /* * remove element * * @param element * @return / @Override public boolean remove(T element) { // start with head Node<T> x = head; // start with index -1 int prevIndex = -1; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { break; } if (element != null && element.equals(x.element)) { break; } x = x.next; prevIndex = i; } // if this linked list is empty if (x == null) { return false; } // if don’t match element if (prevIndex == size - 1) { return false; } Node<T> prev = x.prev; Node<T> next = x.next; // if delete node is head if (prevIndex == -1) { head = next; } // if delete node is tail if (prevIndex == size - 2) { tail = prev; } prev.next = next; next.prev = prev; size–; if (size == 0) { head = tail = null; } // for GC x = null; return true; } /* * remove element by index * * @param index * @return / @Override public T remove(int index) { checkPositionIndex(index); Node<T> x = head; for (int i = 0; i < index; i++) { x = x.next; } // if linked is empty if (x == null) { return null; } Node<T> prev = x.prev; Node<T> next = x.next; // if delete node is head if (index == 0) { head = next; } // if delete node is tail if (index == size - 1) { tail = prev; } prev.next = next; next.prev = prev; size–; if (size == 0) { head = tail = null; } return x.element; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(“Index: " + index + “, Size: " + size); } } /* * set element by index * * @param index * @param element * @return old element / @Override public T set(int index, T element) { Node<T> oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /* * get element by index * * @param index * @return / @Override public T get(int index) { return node(index).element; } /* * get element by index * * @param index * @return / private Node<T> node(int index) { checkPositionIndex(index); if (index < (size >> 1)) { Node<T> x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node<T> x = tail; for (int i = size - 1; i > index; i–) { x = x.prev; } return x; } } /* * clear list / @Override public void clear() { for (Node<T> x = head; x != null; ) { Node<T> next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /* * contain certain element * * @param element * @return / @Override public boolean contains(T element) { if (head == null) { return false; } Node<T> x = head; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { return true; } if (element != null && element.equals(x.element)) { return true; } x = x.next; } return false; } /* * get list size * * @return / @Override public int size() { return size; } /* * Node * * @param <T> */ private class Node<T> { private T element; private Node<T> prev; private Node<T> next; public Node(T element, Node<T> prev, Node<T> next) { this.element = element; this.prev = prev; this.next = next; } }}源代码ArrayList vs LinkedList ArrayListLinkedList插入&删除O(n)O(1)随机访问O(1)O(n)优点连续的内存空间，可以借助CPU的预取机制内存不连续，天然支持动态扩容缺点无法存储大数据，数组扩容耗性能频繁地插入删除操作，会导致内存碎片的增加，导致频繁的GC参考资料http://data.biancheng.net/vie…https://time.geekbang.org/col...https://github.com/phishman35… ...