[数据结构与算法]链表问题 — — 高频面试题【LeetCode - 138】

链表问题

链表面试题常用数据结构和技巧
1）使用容器（哈希表、数组等）
2）快慢指针

1 快慢指针

1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
3）输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
4）输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

//内部类Node
public static class Node{
    private Node next;
    private int value;

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

//奇数长度返回中点，偶数长度返回上中点
public static Node midOrUpMidNode(Node head){
    //不构成快慢指针
    if(head == null || head.next == null || head.next.next == null){
        return head;
    }
    //三个节点及以上
    Node slow = head.next;
    Node fast = head.next.next;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

//奇数长度返回中点，偶数长度返回下中点
public static Node midOrDownMidNode(Node head){
    if(head == null || head.next == null || head.next.next == null){
        return head;
    }
    Node slow = head.next;
    Node fast = head.next;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

//奇数长度返回中点前一个，偶数长度返回上中点前一个
public static Node midOrUpMidPreNode(Node head){
    if(head == null || head.next == null || head.next.next == null){
        return head;
    }
    Node slow = head;
    Node fast = head.next.next;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}


//奇数长度返回中点前一个，偶数长度返回下中点前一个
public static Node midOrDownMidPreNode(Node head){
    if(head == null || head.next == null || head.next.next == null){
        return head;
    }
    Node slow = head;
    Node fast = head.next;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

2 常见面试题

2.1 判断链表是否是回文结构

给定一个单链表的头节点head，判断该链表是否是回文结构

方法一：使用容器【栈结构】
方法二：改变链表结构【反转链表】

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

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

//空间复杂度：O(N)
public static boolean isPalindrome1(Node head){
    Stack<Node> stack = new Stack<>();
    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;
}

//空间复杂度：O(N/2)
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<>();
    //将链表的后半段放入栈中
    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;
}

//空间复杂度:O(1)
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){
        n1 = n1.next; //n1 -> mid
        n2 = n2.next.next;// n2 -> end
    }
    n2 = n1.next;
    n1.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;
    n2 = head;
    boolean res = true;
    while(n1 != null && n2 != null){
        if(n1.value != n2.value){
            res = false;
            break;
        }
        n1 = n1.next;
        n2 = n2.next;
    }
    n1 = n3.next;
    n3.next = null;
    //将链表还原
    while(n1 != null){//recover list
        n2 = n1.next;
        n1.next = n3;
        n3 = n1;
        n1 = n2;
    }
    return res;
}

LeetCode原题：234

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        ListNode n1 = head;
        ListNode n2 = head;
        while(n2.next != null && n2.next.next != null){
            n1 = n1.next;
            n2 = n2.next.next;
        }
        //n1 -> mid
        ListNode n3 = n1.next;
        n1.next = null;
        //反转后半部分链表
        ListNode next = null;
        while(n3 != null){
            next = n3.next;
            n3.next = n1;
            n1 = n3;
            n3 = next;
        }
        n3 = n1;
        ListNode save = n1;
        n1 = head;
        boolean res = true;
        while(n1 != null && n3 != null){
            if(n1.val != n3.val){
                res = false;
                break;
            }
            n1 = n1.next;
            n3 = n3.next;
        }
        
        n3 = save;//回到尾部
        ListNode pre = null;
        //复原链表
        while(n3 != null){
            next = n3.next;
            n3.next = pre;
            pre = n3;
            n3 = next;
        }
        return res;
    }
}

2.2 单向链表划分值【左小、中等、右大】

将单向链表按某值划分成左边小、中间相等、右边大的形式

方法一：将链表放入数组里，在数组上做partition（荷兰国旗问题，快排）
方法二：分成小、中、大三个部分，再把各个部分串起来

2.2.1 使用容器的解法

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

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

//方法一：使用容器
public static Node listPartition1(Node head, int pivot) {
    if (head == null) {
        return head;
    }
    Node cur = head;
    int i = 0;
    while (cur != null) {
        i++;
        cur = cur.next;
    }
    Node[] nodeArr = new Node[i];
    cur = head;
    //将链表放入容器
    for (i = 0; i != nodeArr.length; i++) {
        nodeArr[i] = cur;
        cur = cur.next;
    }
    arrPartition(nodeArr, pivot);
    //重新将链表连起来
    for (i = 1; i != nodeArr.length; i++) {
        nodeArr[i - 1].next = nodeArr[i];
    }
    nodeArr[i - 1].next = null;
    return nodeArr[0];
}

//荷兰国旗问题【”快速排序“】
public static void arrPartition(Node[] nodeArr, int pivot) {
    int small = -1;
    int big = nodeArr.length;
    int index = 0;
    while (index != big) {
        if (nodeArr[index].value < pivot) {
            swap(nodeArr, ++small, index++);
        } else if (nodeArr[index].value == pivot) {
            index++;
        } else {
            swap(nodeArr, --big, index);
        }
    }
}

public static void swap(Node[] nodeArr, int a, int b) {
    Node temp = nodeArr[a];
    nodeArr[a] = nodeArr[b];
    nodeArr[b] = temp;
}

2.2.2 不使用容器

//不使用容器，直接改变链表结构[分成三个部分：小于 等于 大于]
public static Node listPartition2(Node head, int pivot) {
   Node sH = null;//small head
   Node sT = null;//small tail
   Node eH = null;//equal head
   Node eT = null;//equal tail
   Node mH = null;//more head
   Node mT = null;//more tail

   Node next = head;
   while (head != null) {
       //记录head的next
       next = head.next;
       head.next = null;
       if (head.value < pivot) {
           if (sH == null) {
               //小于部分的头尾都没有节点
               sH = head;
               sT = head;
           } else {
               //sH已经有节点了
               sT.next = head;
               sT = head;
           }
       } else if (head.value == pivot) {
           if (eH == null) {
               eH = head;
               eT = head;
           } else {
               eT.next = head;
               eT = head;
           }
       } else {
           if (mH == null) {
               mH = head;
               mT = head;
           } else {
               mT.next = head;
               mT = head;
           }
       }
       head = next;
   }
   //三个区域已经划分好了，开始连接
   if(sH != null){
       sT.next = eH;
   }
   if(eH != null){
       eT.next = mH;
   }
   return sH != null ? sH : (eH == null ? mH : eH);
}

2.3 链表复制（next、rand）【LeetCode - 138】

LeetCode原题：https://leetcode.cn/problems/copy-list-with-random-pointer/
一种特殊的单链表节点如下：

class Node{
	private int value;
	private Node next;
	private Node rand;//随机指向

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

rand指针是单链表节点结构中新增的指针，rand可能指向链表结构中的任意一个节点，也可能指向null
给定一个由Node节点类型组成的无环单链表的头节点head，实现一个函数完成这个链表的复制，并返回新链表的头节点

2.3.1 使用容器map

//解法一：使用容器map
public static Node copyListWithRandom(Node head){
    //key   老节点
    //value 新节点
    HashMap<Node, Node> map = new HashMap<>();
    Node cur = head;
    //建立映射
    while(head != null){
        map.put(cur, new Node(cur.value));//建立新老节点映射关系
        cur = cur.next;
    }
    //完善关系
    cur = head;
    while (cur != null){
        //新节点的next          老节点的下一个
        map.get(cur).next = map.get(cur.next);
        map.get(cur).rand = map.get(cur.rand);
        cur = cur.next;
    }
    return map.get(head);
}

2.3.2 不使用容器

【进阶】：
时间复杂度O（N），额外空间复杂度O（1）

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

//解法：在链表中插入新节点
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        // 1 -> 2 -> 3
        //插入新节点
        Node cur = head;
        Node next = null;//记录原本指向
        while(cur != null){
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
        //1 -> 1' -> 2 -> 2' -> 3 -> 3'
        //设置random
        cur = head;
        Node copy = null;
        while(cur != null){
            next = cur.next.next;//2
            copy = cur.next;// 1'
            copy.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        
        //新旧链表分离
        //1 -> 1' -> 2 -> 2' -> 3 -> 3'
        cur = head;
        Node res = cur.next;//1'
        while(cur != null){
            next = cur.next.next;//2
            copy = cur.next;//1'
            cur.next = next;
            copy.next = next == null ? null : next.next;
            cur = next;
        }
        return res;
    }
}