链表面试题常用数据结构和技巧

注意：
对于笔试，不用太在乎空进依旧切为了时间复杂度。
对于面试，时间复杂度依旧是在第一位，但是一定要找到空间最省的方法。

  1. 使用容器 哈希表数组等
  2. 快慢指针 练习题

链表边界练习题

  • 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
  • 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
  • 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
  • 输入链表头节点，奇数长度放回中点前一个，偶数长度返回下中点前一个
  1. package class09;
  3. import java.util.ArrayList;
  5. public class Code01_LinkedListMid {
  7.     public static class Node {
  8.         public int value;
  9.         public Node next;
  11.         public Node(int v) {
  12.             value = v;
  13.         }
  14.     }
  16.     // head 头
  17.     public static Node midOrUpMidNode(Node head) {
  18.         if (head == null || head.next == null || head.next.next == null) {
  19.             return head;
  20.         }
  21.         // 链表有3个点或以上
  22.         Node slow = head.next;
  23.         Node fast = head.next.next;
  24.         while (fast.next != null && fast.next.next != null) {
  25.             slow = slow.next;
  26.             fast = fast.next.next;
  27.         }
  28.         return slow;
  29.     }
  31.     public static Node midOrDownMidNode(Node head) {
  32.         if (head == null || head.next == null) {
  33.             return head;
  34.         }
  35.         Node slow = head.next;
  36.         Node fast = head.next;
  37.         while (fast.next != null && fast.next.next != null) {
  38.             slow = slow.next;
  39.             fast = fast.next.next;
  40.         }
  41.         return slow;
  42.     }
  44.     public static Node midOrUpMidPreNode(Node head) {
  45.         if (head == null || head.next == null || head.next.next == null) {
  46.             return null;
  47.         }
  48.         Node slow = head;
  49.         Node fast = head.next.next;
  50.         while (fast.next != null && fast.next.next != null) {
  51.             slow = slow.next;
  52.             fast = fast.next.next;
  53.         }
  54.         return slow;
  55.     }
  57.     public static Node midOrDownMidPreNode(Node head) {
  58.         if (head == null || head.next == null) {
  59.             return null;
  60.         }
  61.         if (head.next.next == null) {
  62.             return head;
  63.         }
  64.         Node slow = head;
  65.         Node fast = head.next;
  66.         while (fast.next != null && fast.next.next != null) {
  67.             slow = slow.next;
  68.             fast = fast.next.next;
  69.         }
  70.         return slow;
  71.     }
  73.     public static Node right1(Node head) {
  74.         if (head == null) {
  75.             return null;
  76.         }
  77.         Node cur = head;
  78.         ArrayList<Node> arr = new ArrayList<>();
  79.         while (cur != null) {
  80.             arr.add(cur);
  81.             cur = cur.next;
  82.         }
  83.         return arr.get((arr.size() - 1) / 2);
  84.     }
  86.     public static Node right2(Node head) {
  87.         if (head == null) {
  88.             return null;
  89.         }
  90.         Node cur = head;
  91.         ArrayList<Node> arr = new ArrayList<>();
  92.         while (cur != null) {
  93.             arr.add(cur);
  94.             cur = cur.next;
  95.         }
  96.         return arr.get(arr.size() / 2);
  97.     }
  99.     public static Node right3(Node head) {
  100.         if (head == null || head.next == null || head.next.next == null) {
  101.             return null;
  102.         }
  103.         Node cur = head;
  104.         ArrayList<Node> arr = new ArrayList<>();
  105.         while (cur != null) {
  106.             arr.add(cur);
  107.             cur = cur.next;
  108.         }
  109.         return arr.get((arr.size() - 3) / 2);
  110.     }
  112.     public static Node right4(Node head) {
  113.         if (head == null || head.next == null) {
  114.             return null;
  115.         }
  116.         Node cur = head;
  117.         ArrayList<Node> arr = new ArrayList<>();
  118.         while (cur != null) {
  119.             arr.add(cur);
  120.             cur = cur.next;
  121.         }
  122.         return arr.get((arr.size() - 2) / 2);
  123.     }
  125.     public static void main(String[] args) {
  126.         Node test = null;
  127.         test = new Node(0);
  128.         test.next = new Node(1);
  129.         test.next.next = new Node(2);
  130.         test.next.next.next = new Node(3);
  131.         test.next.next.next.next = new Node(4);
  132.         test.next.next.next.next.next = new Node(5);
  133.         test.next.next.next.next.next.next = new Node(6);
  134.         test.next.next.next.next.next.next.next = new Node(7);
  135.         test.next.next.next.next.next.next.next.next = new Node(8);
  137.         Node ans1 = null;
  138.         Node ans2 = null;
  140.         ans1 = midOrUpMidNode(test);
  141.         ans2 = right1(test);
  142.         System.out.println(ans1 != null ? ans1.value : "无");
  143.         System.out.println(ans2 != null ? ans2.value : "无");
  145.         ans1 = midOrDownMidNode(test);
  146.         ans2 = right2(test);
  147.         System.out.println(ans1 != null ? ans1.value : "无");
  148.         System.out.println(ans2 != null ? ans2.value : "无");
  150.         ans1 = midOrUpMidPreNode(test);
  151.         ans2 = right3(test);
  152.         System.out.println(ans1 != null ? ans1.value : "无");
  153.         System.out.println(ans2 != null ? ans2.value : "无");
  155.         ans1 = midOrDownMidPreNode(test);
  156.         ans2 = right4(test);
  157.         System.out.println(ans1 != null ? ans1.value : "无");
  158.         System.out.println(ans2 != null ? ans2.value : "无");
  160.     }
  162. }

eg：求一个链表的中点位置，技巧
常规方法：
1）遍历链表，求出链表个数，计算出中点值，然后遍历到中点
2）把链表遍历放进容器里去，把中点的索引取出，获取中点
快慢指针：
一个快指针，一个慢指针，快指针每次的步长是慢指针的两，当快指针遍历到链表结尾的时候，慢指针的位置就是链表中点的位置。

题目1： 回文链表问题

题目1： 给定一个单链表的头结点head，请判断该链表是否为回文结构。
回文： 正反一样，eg：12321、1221、123321
1）哈希表，或者数组等采用容器存储链表节点的方法简单。
实现方式：采用容器的方式，第一次遍历链表节点放进栈中，然后再进行第二次遍历，同时伴随出栈，判断每次遍历结果和栈中弹出的值是否相同。正序和逆序都是一样的就是回文。
2）改原链表的方法需要注意边界问题
实现方式： 找到链表中点位置，然后将中点以右的节点next指针反向，同时遍历两个指针进行比较，注意奇偶不同的判断条件。

题目2： 基于题目1的提升题：
给定长度为N的链表头结点H，
如：长度为8的单链表 L1 -> L2 -> L3 -> L4 -> R1 -> R2 -> R3 -> R4
将链表调整为 L1 -> R1 -> L2 -> R2 -> L3 -> R3 -> L4 - R4 进行重新连接。
实现方式：根据题目1，将中点右侧的链表反向连接形成两个链表进行比较，在进行比较的时候可以进行操作，将两个链表的节点重新构成一个新的节点就是这道题的答案。

回文链表代码实现：

package class09;

import java.util.Stack;

/**
 * 回文链表问题
 */
public class Code02_IsPalindromeList {

    public static class Node {
        public int value;
        public Node next;

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

    // need n extra space
    public static boolean isPalindrome1(Node head) {
        Stack<Node> stack = new Stack<Node>();
        Node cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (head != null) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // need n/2 extra space
    public static boolean isPalindrome2(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node right = head.next;
        Node cur = head;
        while (cur.next != null && cur.next.next != null) {
            right = right.next;
            cur = cur.next.next;
        }
        Stack<Node> stack = new Stack<Node>();
        while (right != null) {
            stack.push(right);
            right = right.next;
        }
        while (!stack.isEmpty()) {
            if (head.value != stack.pop().value) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // need O(1) extra space
    public static boolean isPalindrome3(Node head) {
        if (head == null || head.next == null) {
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next != null) { // find mid node
            n1 = n1.next; // n1 -> mid  慢指针
            n2 = n2.next.next; // n2 -> end  快指针
        }
        // n1 中点
        n2 = n1.next; // n2 -> right part first node
        n1.next = null; // mid.next -> null
        Node n3 = null;
        while (n2 != null) { // right part convert 右侧逆序
            n3 = n2.next; // n3 -> save next node
            n2.next = n1; // next of right node convert
            n1 = n2; // n1 move
            n2 = n3; // n2 move
        }
        n3 = n1; // n3 -> save last node
        n2 = head;// n2 -> left first node
        boolean res = true;
        while (n1 != null && n2 != null) { // check palindrome  左右链表比较
            if (n1.value != n2.value) {
                res = false;
                break;
            }
            n1 = n1.next; // left to mid
            n2 = n2.next; // right to mid
        }
        n1 = n3.next;
        n3.next = null;
        while (n1 != null) { // recover list
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }
        return res;
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }
}

题目2： 基于回文链表问题的链表数据分层

将单链表按照某值划分为左边小，中间相等，右边大的形式
1） 将链表放在数组中，在数组上进行partition，荷兰国旗问题。
2） 分成小、中、大三部分，再把各个部分之间串起来

package class09;

import java.util.HashMap;

public class Code04_CopyListWithRandom {

    public static class Node {
        public int value;
        public Node next;
        public Node rand;

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

    /**
     * 使用容器HashMap来进行复制
     * @param head
     * @return
     */
    public static Node copyListWithRand1(Node head) {
        // key 老节点
        // value 新节点，构建新节点存储结构

        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        // 从头开始遍历
        cur = head;
        while (cur != null) {
            // cur 老
            // map.get(cur) 新
            // 新.next ->  cur.next克隆节点找到
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // copy node and link to every node
        // 1 -> 2
        // 1 -> 1' -> 2
        while (cur != null) {
            // cur 老 next 老的下一个
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        // set copy node rand
        // 1 -> 1' -> 2 -> 2'
        while (cur != null) {
            // cur 老
            // cur.next 新 copy
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }
        // head head.next
        Node res = head.next;
        cur = head;
        // split
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }

    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

题目3：常见面试题-next & random结构节点

一种特殊的单链表节点类型为：

Class Node{
    int vlaue;
    Node next;
    Node rand;
    Node(int value) {value = value}
}
  • rand指针是单链表节点结构中新增的指针，rand可能指向单链表中的任意一个节点，也可能指向为NULL
  • 给定一个由Node节点类型组成的无环单链表的头结点head，请实现一个函数完成这个链表的复制，并且返回新链表的头结点

【要求】时间复杂度为O(N)，空间复杂度为O(1)

思路：复制节点插入到对应原节点的后面，使源节点和复制节点通过源节点.next相互绑定，然后给遍历取出每一对节点，对复制节点的rand进行赋值，n.rand= n.rand.next` ,之后将链表中的源节点断开链接，只剩下复制之后的节点。

代码实现：

package class09;

import java.util.HashMap;

public class Code04_CopyListWithRandom {

    public static class Node {
        public int value;
        public Node next;
        public Node rand;

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

    /**
     * 使用容器HashMap来进行复制
     * @param head
     * @return
     */
    public static Node copyListWithRand1(Node head) {
        // key 老节点
        // value 新节点，构建新节点存储结构

        HashMap<Node, Node> map = new HashMap<Node, Node>();
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }

        // 从头开始遍历
        cur = head;
        while (cur != null) {
            // cur 老
            // map.get(cur) 新
            // 新.next ->  cur.next克隆节点找到
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        // copy node and link to every node
        // 1 -> 2
        // 1 -> 1' -> 2
        while (cur != null) {
            // cur 老 next 老的下一个
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        // set copy node rand
        // 1 -> 1' -> 2 -> 2'
        while (cur != null) {
            // cur 老
            // cur.next 新 copy
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }
        // head head.next
        Node res = head.next;
        cur = head;
        // split
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }

    public static void printRandLinkedList(Node head) {
        Node cur = head;
        System.out.print("order: ");
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
        cur = head;
        System.out.print("rand:  ");
        while (cur != null) {
            System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

}