数据结构面试题：链表
1. 遍历一遍确定单链表的中间节点
使用两个指针a、b，a每次移动一个节点，b每次移动两个节点，当b指向末尾时，a指向中间节点。
public class LinkedListTest {
public static void main(String args[]) {
LinkedList linkedList = new LinkedList();
LinkedList.Node head = linkedList.head();
linkedList.add( new LinkedList.Node("1"));
linkedList.add( new LinkedList.Node("2"));
linkedList.add( new LinkedList.Node("3"));
linkedList.add( new LinkedList.Node("4"));
LinkedList.Node current = head;
int length = 0;
LinkedList.Node middle = head;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : " + middle);
}
}
class LinkedList{
private Node head;
private Node tail;
public LinkedList(){
this.head = new Node("head");
tail = head;
}
public Node head(){
return head;
}
public void add(Node node){
tail.next = node;
tail = node;
}
public static class Node{
private Node next;
private String data;
public Node(String data){
this.data = data;
}
public String data() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node next() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String toString(){
return this.data;
}
}
}
Output:
length of LinkedList: 4
middle element of LinkedList: 2
2. 判断链表是否为循环链表
- 准备快速和慢速两个指针
- 在每次循环中快速指针移动两个节点，慢速指针移动一个节点
- 如果快速指针和慢速指针相遇则链表包含循环
- 如果快速指针指向null或快速指针的下一个节点为null，则链表不是循环的
public class LinkedList {
private Node head;
public LinkedList() { this.head = new Node("head"); }
public Node head() { return head;}
public void appendIntoTail(Node node) {
Node current = head;
while(current.next() != null){
current = current.next();
}
current.setNext(node);
}
public boolean isCyclic(){
Node fast = head;
Node slow = head;
while(fast!= null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow ){
return true;
}
}
return false;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Node current = head.next();
while(current != null){
sb.append(current).append("-->");
current = current.next();
}
sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node
return sb.toString();
}
public static class Node {
private Node next;
private String data;
public Node(String data) {
this.data = data;
}
public String data() { return data; }
public void setData(String data) { this.data = data;}
public Node next() { return next; }
public void setNext(Node next) { this.next = next; }
@Override
public String toString() {
return this.data;
}
}
}
3. 如何找到带循环的链表中循环的开始位置
遍历节点，第一个出现两次的节点就是循环的开始位置。
4. 如何翻转链表
public class SinglyLinkedList {
private Node head;
public void append(T data){
if(head == null){
head = new Node(data);
return;
}
tail().next = new Node(data);
}
private Node tail() {
Node tail = head;
// Find last element of linked list known as tail
while(tail.next != null){
tail = tail.next;
}
return tail;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Node current = head;
while(current != null){
sb.append(current).append("-->");
current = current.next;
}
if(sb.length() >=3){
sb.delete(sb.length() - 3, sb.length());
}
return sb.toString();
}
// 循环
public void reverseIteratively() {
Node current = head;
Node previous = null;
Node forward = null;
while(current.next != null){
forward = current.next;
current.next = previous;
previous = current;
current = forward;
}
head = current;
head.next = previous;
}
private Node reverseRecursively(Node node){
Node newHead;
if((node.next == null)){
return node;
}
newHead = reverseRecursively(node.next);
node.next.next = node;
node.next = null;
return newHead;
}
// 递归
public void reverseRecursively(){
head = reverseRecursively(head);
}
private static class Node {
private Node next;
private T data;
public Node(T data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
}
5. 移除未排序链表中的重复结点
要想移除链表中的重复结点，我们需要设法记录有哪些是重复的。这里只要用到一个简单的散列表。
在下面的解法中，直接迭代访问整个链表，将每个结点加入散列表。若发现有重复元素，则将该结点从链表中移除，然后继续迭代。这个题目使用了链表，因此只需扫描一次就能搞定。
public static void deleteDups(LinkedListNode n) {
Hashtable table = new Hashtable();
LinkedListNode previous = null;
while (n != null) {
if (table.containsKey(n.data)) {
previous.next = n.next;
} else {
table.put(n.data, true);
previous = n;
}
n = n.next;
}
}
6. 移除未排序链表中的重复结点，不使用缓存区
如不借助额外的缓冲区，可以用两个指针来迭代：current迭代访问整个链表，runner用于检查后续的结点是否重复。空间复杂度为O(1)，但时间复杂度为O(n^2)。
public static void deleteDups(LinkedListNode head) {
if (head == null) return;
LinkedListNode current = head;
while (current != null) {
/* 移除后续值相同的所有结点*/
LinkedListNode runner = current;
while (runner.next != null) {
if (runner.next.data == current.data) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
current = current.next;
}
}
7. 如何确定链表长度
- 循环
public int length(){
int count=0;
Node current = this.head;
while(current != null){
count++;
current=current.next()
}
return count;
}
- 递归
public int length(Node current){
if(current == null){ //base case
return 0;
}
return 1+length(current.next());
}
8. 找出单向链表中倒数第k个结点
下面会以递归和非递归的方式解决这个问题。一般来说，递归解法更简洁，但效率比较差。例如，就这个问题来说，递归解法的代码量大概只有迭代解法的一半，但要占用O(n)空间，其中n为链表结点个数。
注意，在下面的解法中，k定义如下：传入k = 1将返回最后一个结点，k = 2返回倒数第2个结点，依此类推。当然，也可以将k定义为k = 0返回最后一个结点。
解法1：链表长度已知
若链表长度已知，那么，倒数第k个结点就是第(length - k)个结点。直接迭代访问链表就能找到这个结点。不过，这个解法太过简单了，不大可能是面试官想要的答案。
解法2：递归
这个算法会递归访问整个链表，当抵达链表末端时，该方法会回传一个置为0的计数器。之后的每次调用都会将这个计数器加1。当计数器等于k时，表示我们访问的是链表倒数第k个元素。
实现代码简洁明了，前提是我们要有办法通过栈“回传”一个整数值。可惜，我们无法用一般的返回语句回传一个结点和一个计数器，那该怎么办？
- 方法A：不返回该元素
一种方法是对这个问题略作调整，只打印倒数第k个结点的值。然后，直接通过返回值传回 计数器值。
public static int nthToLast(LinkedListNode head, int k) {
if (head == null) {
return 0;
}
int i = nthToLast(head.next, k) + 1;
if (i == k) {
System.out.println(head.data);
}
return i;
}
当然，只有得到面试官的首肯，这个解法才算有效。
- 方法B：使用C++
第二种解法是使用C++，并通过引用传值。这样一来，我们就可以返回结点值，而且也能通 过传递指针更新计数器。
node* nthToLast(node* head, int k, int& i) {
if (head == NULL) {
return NULL;
}
node * nd = nthToLast(head->next, k, i);
i = i + 1;
if (i == k) {
return head;
}
return nd;
}
- 方法C：创建包裹类
前面提到，这里的难点在于我们无法同时返回计数器和索引值。如果用一个简单的类（或一个单元素数组）包裹计数器值，就可以模仿按引用传递。
public class IntWrapper {
public int value = 0;
}
LinkedListNode nthToLastR2(LinkedListNode head, int k, IntWrapper i) {
if (head == null) {
return null;
}
LinkedListNode node = nthToLastR2(head.next, k, i);
i.value = i.value + 1;
if (i.value == k) { // 找到倒数第k个元素
return head;
}
return node;
}
因为有递归调用，这些递归解法都需要占用O(n)空间。
还有不少其他解法这里并未提及。我们可以将计数器存放在静态变量中，或者，可以创建一个类，存放结点和计数器，并返回这个类的实例。不论选用哪种解法，我们都要设法更新结点和计数器，并在每层递归调用的栈都能访问到。
解法3：迭代法
一种效率更高但不太直观的解法是以迭代方式实现。我们可以使用两个指针p1和p2，并将它们指向链表中相距k个结点的两个结点，具体做法是先将p1和p2指向链表首结点，然后将p2向前移动k个结点。之后，我们以相同的速度移动这两个指针，p2会在移动LENGTH - k步后抵达链表尾结点。此时，p1会指向链表第LENGTH - k个结点，或者说倒数第k个结点。
下面的代码实现了该算法。
LinkedListNode nthToLast(LinkedListNode head, int k) {
if (k <= 0) return null;
LinkedListNode p1 = head;
LinkedListNode p2 = head;
// p2向前移动k个结点
for (int i = 0; i < k - 1; i++) {
if (p2 == null) return null; // 错误检查
p2 = p2.next;
}
if (p2 == null) return null;
/* 现在以同样的速度移动p1和p2，当p2抵达链表末尾时，
* p1刚好指向倒数第k个结点*/
while (p2.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
这个算法的时间复杂度为O(n)，空间复杂度为O(1)。