WHCSRL 技术网

算法进阶之路(五):链表面试题常用数据结构和技巧

一、链表解析思路

最常用的主要是两大解题思路:
(1):双指针法(快慢指针)
(2):使用容器(数组、哈希表等)

二、小试牛刀

1.面试题:

在这里插入图片描述

2.**解题思路:**通过双指针法可以简单有效的解答此类问题,定义一个快指针,每次跳两个节点,定义一个慢指针,每次跳一个节点,当快指针调到末尾时,慢指针此时在中点附近。以上四个小题都可以通过这个思路解决,唯一不同的是,指针初始化位置的不同。
3.解题代码:

针对小题1的解题代码:

public class LinkedListTest {

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

        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 fast = head;
        Node slow = head;
        // 当快指针走到链表末尾时,跳出循环
        while(fast.next!=null&&fast.next.next!=null){
            // 快指针每次跳两步
            fast = fast.next.next;
            // 慢指针每次跳一步
            slow = slow.next;
        }
        return slow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

针对小题2的解题代码:
在这里插入图片描述
3题和4题都是类似的解法,留给大家自己解决,这里不再陈述。

三、入门

1.面试题:

在这里插入图片描述
解释:什么是回文结构,例如12321,123321这种正着念和倒着念一样的结构,就是回文结构:

2.解题思路:

1.先看第一种解法,我们知道栈的结构是先进后出的,因此可以利用栈的结构特点,遍历链表将所有的节点全部压栈,然后再从链表头节点开始,和出栈的节点一一对比,只要全部相等,就是回文结构,代码如下:

    public static boolean isPalindrome1(Node head){
        // 从头节点开始遍历链表,依次压栈
        final Stack<Node> stack = new Stack<>();
        Node start = head;
        while(start!=null){
            stack.push(start);
            start = start.next;
        }
        // 从栈中取出元素和链表一一比对
        while(!stack.isEmpty()){
            if(stack.pop().value!=head.value){
                return false;
            }
            head= head.next;
        }
        return true;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

2.第一种解法使用了栈的结构,相当于空间复杂度O(N),我们使用空间复杂度O(1)来解决下这个问题,基本思路是快慢指针的方法,当快指针指到链表尾部时,慢指针指到链表的中间,如果是偶数个节点,就指到上中点,此时将上中点的下一个节点指向null,链表后半部分的节点反转,反转完成后,分别从头部和尾部一一比对前半部分和后半部分的节点。
解题代码:

    public static boolean isPalindrome2(Node head){
        if(head==null||head.next==null){
            return true;
        }
        // 分别定义快指针和慢指针
        Node n2 = head;
        Node n1 = head;
        // 当快指针走到链表末尾时,跳出循环
        while(n2.next!=null&&n2.next.next!=null){
            // 快指针每次跳两步
            n2 = n2.next.next;
            // 慢指针每次跳一步
            n1 = n1.next;
        }

        // 将链表的后半部分进行反转
        n2 = n1.next;
        n1.next=null;
        // 临时存储下一个节点
        Node n3 =null;
        // 对链表进行反转
        while(n2!= null){
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 = n3;
        }
        // 保存尾部节点
        n3 = n1;
        // n1指向头节点
        n1 = head;
        boolean res = true;
        // 分别从n1和n2开始对比
        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){
            n2 = n1.next;
            n1.next = n1;
            n3 = n1;
            n1 = n2;
        }
        return res;

    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

测试方法:

    public static void main(String[] args) {
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next= new Node(3);
        node1.next.next.next= new Node(2);
        node1.next.next.next.next= new Node(1);
        final boolean b = isPalindrome2(node1);
        System.out.println(b);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

最终全部验证通过。

四、进阶

1.面试题:

在这里插入图片描述

2.解题思路:

第一种解法,将链表转成数组,使用基于荷兰国旗的快排思想,排序好后,再依次放入链表中,这里不再做编码,想自己写一下的,可以参考算法进阶之路(二)
第二种解法:使用六个变量,分别存储小于区域的head和tail,等于区域的head和tail,大于区域的head和tail

    public static Node listPartition(Node head,int pivot){
        Node sH = null;
        Node sT = null;
        Node eH = null;
        Node eT = null;
        Node mH = null;
        Node mT = null;
        Node next = null;
        while(head!=null){
            next = head.next;
            head.next=null;
            final int value = head.value;
            // 小于区域
            if(value<pivot){
                // 首次进入
                if(sH==null){
                    sH = head;
                    sT = head;
                }else{
                    sT.next=head;
                    sT = head;
                }
            // 等于区域
            }else if(value==pivot){
                // 首次进入
                if(eH==null){
                    eH = head;
                    eT = head;
                }else{
                    eT.next=head;
                    eT = head;
                }
            // 大于区域
            }else if(value>pivot){
                // 首次进入
                if(mH==null){
                    mH = head;
                    mT = head;
                }else{
                    mT.next=head;
                    mT = head;
                }
            }
            head = next;
        }
        // 如果有小于区域
        if(sT!=null){
            sT.next = eH;
            // 等于区域不存在的话,等于区域的尾巴去连接大于区域的头,否则使用小于区域的尾巴去连接大于区域的头
            eT=eT==null?sT:eT;
        }
        // 如果小于区域和等于区域,不是都没有
        if(eT!=null){
            eT.next = mH;
        }
        return sH!=null?sH:(eH!=null?eH:mH);
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
推荐阅读