算法训练营——链表的题目的常考

链表的面试常考类型的题目 链表的翻转

package 牛客网名企面试笔试问题2021;

import java.util.List;

/**
 * @Classname 链表的翻转
 * @Description TODO
 * @Date 2021/3/8 12:21
 * @Created by xjl
 */
public class 链表的翻转 {
    public class ListNode {
        int val;
        ListNode next;

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

    public ListNode reverse(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode future = curr.next;
            curr.next = pre;
            pre.next = curr;
            curr.next = future;
        }
        return pre;
    }

    public ListNode reverse2(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dumpy = new ListNode(0);
        dumpy.next = head;

        ListNode pre = dumpy;
        ListNode curr = head;

        while (curr != null && curr.next != null) {
            ListNode future = curr.next;
            curr.next=future.next;
            future.next=dumpy.next;
            pre.next=future;
        }
        return dumpy.next;
    }
}

链表是否有环（判断是否口在哪里）

package 牛客网名企面试笔试问题2021;

/**
 * @Classname 判断是否有环
 * @Description TODO
 * @Date 2021/3/8 12:31
 * @Created by xjl
 */
public class 判断是否有环 {
    public class ListNode {
        int val;
        ListNode next;

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

    public boolean cycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        ListNode low = head;
        while (fast != null && fast.next != null) {
            //快慢指针的效果
            fast = fast.next.next;
            low = low.next;
            if (low == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * @description TODO  判断环的入口在哪里
     * @param: head
     * @date: 2021/3/8 12:34
     * @return: 牛客网名企面试笔试问题2021.判断是否有环.ListNode
     * @author: xjl
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode low = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if (fast == low) {
                //表示有环了 去判断环的入口
                fast = head;
                while (fast != low) {
                    fast = fast.next;
                    low = low.next;
                }
                return fast;
            }
        }
        //表示没有环
        return null;
    }
}

合并链表

package 牛客网名企高频面试题复现代码2020;

/**
 * @Classname 合并链表
 * @Description TODO
 * @Date 2020/12/21 14:53
 * @Created by xjl
 */
public class 合并链表 {

    /**
     * @description TODO  链表的都是有序的
     * @param: head1
     * @param: head2
     * @date: 2020/12/21 14:58
     * @return: 复现代码.合并链表.ListNode
     * @author: xjl
     */
    public ListNode merge2(ListNode head1, ListNode head2) {
        if (head1 == null && head2 != null) {
            return head2;
        }
        if (head1 != null && head2 == null) {
            return head1;
        }
        if (head1 == null && head2 == null) {
            return null;
        }

        ListNode dumpy = new ListNode(0);
        ListNode curr = dumpy;

        ListNode curr1 = head1;
        ListNode curr2 = head2;

        while (curr1 != null && curr2 != null) {
            if (curr1.val >= curr2.val) {
                curr.next = curr2;
                curr2 = curr2.next;
            } else {
                curr.next = curr1;
                curr1 = curr1.next;
            }
            curr = curr.next;
        }
        while (curr1 != null) {
            curr.next = curr1;
            curr = curr.next;
            curr1 = curr.next;
        }
        while (curr2 != null) {
            curr.next = curr2;
            curr = curr.next;
            curr2 = curr.next;
        }
        return dumpy.next;
    }

    /**
     * @description TODO 采用的是归并的思想来实现的对链表的合并
      * @param: l1
     * @param: l2
     * @date: 2021/3/8 12:49
     * @return: 牛客网名企高频面试题复现代码2020.合并链表.ListNode
     * @author: xjl
    */
    public ListNode merge(ListNode l1, ListNode l2) {
        // 创建一个新的链表
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return pre.next;
    }

    public class ListNode {
        int val;
        ListNode next;

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

链表的k组翻转

package 牛客网名企面试笔试代码复现2021;

/**
 * @Classname 链表k个翻转
 * @Description TODO
 * @Date 2021/2/25 22:20
 * @Created by xjl
 */
public class 链表k个翻转 {

    public class ListNode{
        int val;
        ListNode next;
        public ListNode (int val){
            this.val=val;
        }
    }
    /**
     * @description TODO  将给出的链表中的节点每 k\ k k 个一组翻转，返回翻转后的链表  如果链表中的节点数不是 k\ k k 的倍数，将最后剩下的节点保持原样  你不能更改节点中的值，只能更改节点本身
     *
      * @param: head
     * @param: k
     * @date: 2021/2/25 22:24
     * @return: 牛客网名气面试笔试问题2021.链表k个翻转.ListNode
     * @author: xjl
    */
    public ListNode reverseKGroup (ListNode head, int k) {
        //边界情况的
        if (head==null||head.next==null||k 0) {
            cur.next = new ListNode(carry);
        }
        return reverse(head.next);
    }
    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    
}

链表的公共节点

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
         Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        while (pHead1 != null) {
            stack1.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            stack2.add(pHead2);
            pHead2 = pHead2.next;
        }
        ListNode ans = null;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() == stack2.peek()) {
                ans = stack1.peek();
                stack1.pop();
                stack2.pop();
            } else {
                break;
            }
        }
        return ans;
    }
}

链表的无序单链表排序

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return ;
        }
        //快慢指针，找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode start = head;
        ListNode end1 = mid.next;
        mid.next = null;//断链
        ListNode end = reverList(end1);
        //插入
        while(start != null && end!=null){
            ListNode next1 = start.next;
            ListNode next2 = end.next;
            start.next = end;
            end.next = next1;
            start = next1;
            end = next2;
        }
        return ;
    }
    private ListNode reverList(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }
}

链表是否是回文结构

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        ArrayList list = new ArrayList();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        for (int i = 0; i < list.size() / 2; i++) {
            if (!list.get(i).equals(list.get(list.size() - 1 - i))) {
                return false;
            }
        }
        return true;
    }
}

链表制定区间的翻转

 

删除链表的制定的元素

package 牛客网名企高频面试题复现代码2020;

/**
 * @Classname 删除指定的节点
 * @Description TODO
 * @Date 2020/12/22 15:01
 * @Created by xjl
 */
public class 删除指定的节点 {

    /**
     * @description TODO  删除的是倒数的第n节点  先计算是的个数 然后在的前一个停下来 在将前一个指向下一个的下一个的节点
     * @param: val
     * @date: 2020/12/22 15:19
     * @return:
     * @author: xjl
     */
    public ListNode deone(ListNode head, int n) {
        //计算右多少个节点
        ListNode n1 = head;
        int count = 0;
        while (n1 != null) {
            count++;
            n1 = n1.next;
        }

        ListNode dumy = new ListNode(0);
        dumy.next = head;
        ListNode curr = dumy;
        //在删除一个节点
        count = count - n;
        while (count > 0) {
            curr = curr.next;
            count--;
        }
        curr.next = curr.next.next;
        return dumy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

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

删除链表的重复元素

package 牛客网名企高频面试题复现代码2020;

import org.junit.Test;

/**
 * @Classname 删除链表的重复元素
 * @Description TODO
 * @Date 2020/12/21 15:06
 * @Created by xjl
 */
public class 删除链表的重复元素 {

    public ListNode delete(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode curr = head;
        while (curr.next != null) {
            if (curr.val == curr.next.val) {
                curr.next = curr.next.next;
            } else {
                curr = curr.next;
            }
        }
        return head;
    }

    public ListNode de(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            ListNode future = curr.next;
            if (future.val == curr.val) {
                curr.next = future.next;
            } else {
                curr = curr.next;
            }
        }
        return head;
    }

    @Test
    public void test() {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(1);
        ListNode s3 = new ListNode(2);
        ListNode s4 = new ListNode(3);
        ListNode s5 = new ListNode(3);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;

        ListNode res = delete(s1);

        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    public class ListNode {
        int val;
        ListNode next;

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

链表的重新排列

package 牛客网名企高频面试题复现代码2020;

/**
 * @Classname 合并链表
 * @Description TODO
 * @Date 2020/12/21 14:53
 * @Created by xjl
 */
public class 合并链表 {

    /**
     * @description TODO  链表的都是有序的
     * @param: head1
     * @param: head2
     * @date: 2020/12/21 14:58
     * @return: 复现代码.合并链表.ListNode
     * @author: xjl
     */
    public ListNode merge2(ListNode head1, ListNode head2) {
        if (head1 == null && head2 != null) {
            return head2;
        }
        if (head1 != null && head2 == null) {
            return head1;
        }
        if (head1 == null && head2 == null) {
            return null;
        }

        ListNode dumpy = new ListNode(0);
        ListNode curr = dumpy;

        ListNode curr1 = head1;
        ListNode curr2 = head2;

        while (curr1 != null && curr2 != null) {
            if (curr1.val >= curr2.val) {
                curr.next = curr2;
                curr2 = curr2.next;
            } else {
                curr.next = curr1;
                curr1 = curr1.next;
            }
            curr = curr.next;
        }
        while (curr1 != null) {
            curr.next = curr1;
            curr = curr.next;
            curr1 = curr.next;
        }
        while (curr2 != null) {
            curr.next = curr2;
            curr = curr.next;
            curr2 = curr.next;
        }
        return dumpy.next;
    }

    /**
     * @description TODO 采用的是归并的思想来实现的对链表的合并
      * @param: l1
     * @param: l2
     * @date: 2021/3/8 12:49
     * @return: 牛客网名企高频面试题复现代码2020.合并链表.ListNode
     * @author: xjl
    */
    public ListNode merge(ListNode l1, ListNode l2) {
        // 创建一个新的链表
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return pre.next;
    }

    public class ListNode {
        int val;
        ListNode next;

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

链表的奇偶的重新排列

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode oddEvenList (ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenhead = head.next;

        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        //将节点反过来
        odd.next = evenhead;
        return head;
    }
}

约瑟夫环的问题

/**
     * @description TODO   f(n,m)=(f(n-1,m)+m)%n
     * @param: n
     * @param: m
     * @date: 2020/12/22 18:55
     * @return: int
     * @author: xjl
     */
    public int ysf1(int n, int m) {
        //通过的数学公式
        if (n == 0 || m == 0) {
            return -1;
        }
        int last = 0;
        for (int i = 2; i