【面试必刷101】链表

摘要

【面试必刷101】系列blog目的在于总结面试必刷101中有意思、可能在面试中会被考到的习题。总结通用性的解题方法，针对特殊的习题总结思路。既是写给自己复习使用，也希望与大家交流。

【面试必刷101】递归/回溯算法总结I（十分钟理解回溯算法）
【面试必刷101】递归/回溯算法总结II（十分钟刷爆回溯算法题）

1 链表基础知识

单链表

public class ListNode {
    
    int val;
    ListNode next = null;
    
    ListNode(int val) {
    
        this.val = val;
    }
}

双链表

public class ListNode {
    
    int val;
    ListNode next = null;
    ListNode pre = null;
    ListNode(int val) {
    
        this.val = val;
    }
}

链表这类题感觉出的比较少，注意以下几个题型就可以了。

2 面试必刷习题

2.1 k个一组反转链表

普通的反转链表：

很简单的一张图，就是将当前节点指向前一个节点，然后将当前节点变成下一个节点来进行遍历。

import java.util.*;
public class Solution {
    
public class Solution {
    
    public ListNode ReverseList(ListNode cur) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

然后来看链表中每k个节点一组翻转。

首先可以用递归来实现：每k个一组其实可以先做后面的再做前面的，大问题由很多小问题组成。
然后小问题可以用简单的链表翻转来做。具体看代码，还是很值得学习的。

import java.util.*;
public class Solution {
    
    public ListNode reverseKGroup (ListNode head, int k) {
    
        if (head == null || head.next == null) return head;
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
    
            if (tail == null) {
    
                return head;
            }
            tail = tail.next;
        }
        // 翻转前k个元素
        ListNode newHead = reverse(head, tail);
        // head已经是最后一个元素了。这个递归很有灵性。
        head.next = reverseKGroup(tail, k);
        return newHead;
    }
    // 反转[head, tail)
    public ListNode reverse (ListNode cur, ListNode tail) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != tail) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2.2 合并k个链表

题目链接：BM5 合并k个已排序的链表

为啥这道题值得一做呢？主要考察点有三个：

• 合并策略是啥？ 基于归并排序思路的两两合并；优先队列。
• 怎么合并两个有序链表？ 建立一个头结点，谁小就插入谁。

import java.util.*;
public class Solution {
    
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
    
        return mergeList(lists, 0, lists.size() - 1);
    }
    
    public ListNode mergeList(ArrayList<ListNode> list, int l, int r) {
    
        if (l== r) {
    
            return list.get(l);
        }
        if (l > r) {
    
            return null;
        }
        int mid = l + ((r - l) >> 1);
        ListNode left = mergeList(list, l, mid);
        ListNode right = mergeList(list, mid + 1, r);
        return merge2Lists(left, right);
    }
    
    // 合并两个链表
    public ListNode merge2Lists(ListNode list1, ListNode list2) {
    
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
    
            if (list1.val > list2.val) {
    
                cur.next = list2;
                list2 = list2.next;
            } else {
    
                cur.next = list1;
                list1 = list1.next;
            }
            cur = cur.next;
        }
        if (list1 != null) cur.next = list1;
        if (list2 != null) cur.next = list2;
        return head.next;
    }
}

2.3 链表相加

题目链接：链表相加（二）

乍一眼看起来好难呀？该从哪里开始相加呢？不清楚。为啥不清楚，因为从next Node找不到pre Node，这就是单链表的特点。但是，如果翻转之后就很好做了。

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * } */

public class Solution {
    
    /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */
    public ListNode addInList (ListNode head1, ListNode head2) {
    
        ListNode h1 = reverse(head1);
        ListNode h2 = reverse(head2);
        int tag = 0;
        int val = 0;
        ListNode cur = null, pre = null;
        while (h1 != null || h2 != null) {
    
            if (h1 != null) {
    
                val += h1.val;
                h1 = h1.next;
            }
            if (h2 != null) {
    
                val += h2.val;
                h2 = h2.next;
            }
            val += tag;
            if (val >= 10) {
    
                tag = 1;
                val = val % 10;
            } else {
    
                tag = 0;
            }
            cur = new ListNode(val);
            val = 0;
            cur.next = pre;
            pre = cur;
        }
        if (tag == 1) {
    
            cur = new ListNode(1);
            cur.next = pre;
        }
        return cur;
    }
    
    public ListNode reverse (ListNode cur) {
    
        ListNode pre = null;
        ListNode next = null;
        while (cur != null) {
    
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2.4 单链表的排序

题目链接：BM12单链表的排序。

2.5 判断一个链表是否是回文结构

2.6 删除链表的重复元素