美文网首页数据结构和算法
链表问题汇总

链表问题汇总

作者: 小鱼嘻嘻 | 来源:发表于2018-12-02 23:15 被阅读11次
写在前面

记录常见的链表操作，基本可以秒杀一切面试题(虽然这不是我们的本意)。这些问题都来源于LeetCode，我会给出相应的解法和说明。并且我会对链表问题做一个分类，固定问题固定套路。

1 链表翻转 level1 倒序输出 level2 区间倒序 level3 k个元素倒序
2 有序链表去除重复元素 level1 除去重复元素 level2 重复出现元素都去掉
3 有序链接求和 level1 满10右进位 level2 满10左进位
3 链表移位 level 移动k个位置
4 快慢指针 level0 链表中间元素 level1 判断链表是否有环 level2 判断环的起始位置
5 链表排序
6 链表元素加1
7 链表奇偶分类
8 是否是回文链表
9 两个链表公共部分
10 链表分割为n段

链表翻转
  • 整个链表翻转
    翻转链表思路：
    第一：定义两个节点，pre和cur;
    第二：遍历链表，cur=root;关键步骤：root=root.next;cur.next=pre;pre = cur;简单来说就是当前节点的next指向pre，pre指向下一个节点。
    在写代码之前最好在纸上画个图，自己走几遍。
package com.xiyu.sentinel.newlinkednode;

/**
 * 链表翻转
 *
 * @author yuxi
 */
public class ReverseNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
        //iter
        ListNode root = head;
        while (root != null) {
            System.out.print(root.val + "-->");
            root = root.next;
        }
        root = head;
        System.out.println();
        System.out.println("reverse.....");
        // reverse
        ListNode reverse = reverseNode(root);
        while (reverse != null) {
            System.out.print(reverse.val + "-->");
            reverse = reverse.next;
        }
    }

    /**
     * 链表翻转
     *
     * @param root
     * @return
     */
    private static ListNode reverseNode(ListNode root) {
        if (root == null) {
            return null;
        }
        //定义连个节点 一个前置节点，一个当前节点；
        ListNode pre = null;
        ListNode cur;
        while (root != null) {
            cur = root;
            root = root.next;
            cur.next = pre;
            pre = cur;
        }

        return pre;
    }
}
  • 链表部分翻转
    翻转K个思路：
    第一：定义pre1,cur1,pre2,cur2四个节点,count节点个数；
    第二：遍历链表找到需要翻转的位置m,pre1,pre2指向m的前一个，cur1,cur2指向m;
    第三：使用pre2和cur2翻转(n-m)个链表元素，pre2指向n,cur2指向n的笑一个节点
    第四：把翻转后的链表和整个链表重新连起来，pre1.next=pre2;cur2.next=root;
package com.xiyu.sentinel.newlinkednode;

/**
 * 翻转k个节点
 *
 * @author yuxi
 */
public class ReverseNodeK {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, null))));
        //iter
        ListNode root = head;
        while (root != null) {
            System.out.print(root.val + "-->");
            root = root.next;
        }
        root = head;
        System.out.println();
        System.out.println("reverse....");
        // reverse
        ListNode reverse = reverseNodeK(root, 2, 3);
        while (reverse != null) {
            System.out.print(reverse.val + "-->");
            reverse = reverse.next;
        }
    }

    /**
     * 将第m 到n个节点翻转
     *
     * @param root
     * @param m
     * @param n
     * @return
     */
    private static ListNode reverseNodeK(ListNode root, int m, int n) {
        if (root == null) {
            return null;
        }
        if (m > n) {
            return null;
        }
        ListNode ret = new ListNode(-1);
        ret.next = root;
        // 定义当前节点和前置节点，为了第二部分翻转之后连接做准备
        ListNode pre1 = ret;
        ListNode cur1 = root;
        int count = 1;
        while (count < m) {
            pre1 = root;
            root = root.next;
            cur1 = root;
            count++;
        }

        //处理翻转节点
        ListNode pre2 = pre1;
        ListNode cur2;
        int count2 = m;
        while (count2 <= n && root != null) {
            cur2 = root;
            root = root.next;
            cur2.next = pre2;
            pre2 = cur2;
            count2++;
        }

        // 链表重新组装
        pre1.next = pre2;
        cur1.next = root;
        return ret.next;
    }
}
链表去除重复元素

前提条件：链表要求是有序的
第一：定义两个节点 pre cur;
第二：如果当前节点等于当前节点下一个循环，找到不相等节点
然后，pre.next = root; pre = pre.next; root = root.next;

  • 保留重复元素当中的一个
package com.xiyu.sentinel.newlinkednode;

/**
 * 除去链表重复元素【保留一个】
 *
 * @author yuxi
 */
public class DuplicateNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        //iter
        ListNode root = head;
        while (root != null) {
            System.out.print(root.val + "-->");
            root = root.next;
        }
        root = head;
        System.out.println();
        ListNode noDuplicate = duplicateNode(root);
        while (noDuplicate != null) {
            System.out.print(noDuplicate.val + "-->");
            noDuplicate = noDuplicate.next;
        }
    }

    /**
     * 除去重复元素
     *
     * @param root
     * @return
     */
    private static ListNode duplicateNode(ListNode root) {
        if (root == null) {
            return null;
        }
        ListNode ret = new ListNode(-1);
        ListNode pre = ret;
        ret.next = root;
        while (root != null) {
            while (root != null && root.next != null && root.val == root.next.val) {
                root = root.next;
            }
            pre.next = root;
            pre = pre.next;
            root = root.next;
        }
        return ret.next;
    }
}
  • 重复元素一个都不保留
package com.xiyu.sentinel.newlinkednode;

/**
 * 除去链表重复元素【保留一个】
 *
 * @author yuxi
 */
public class DuplicateNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        //iter
        ListNode root = head;
        while (root != null) {
            System.out.print(root.val + "-->");
            root = root.next;
        }
        root = head;
        System.out.println();
        ListNode noDuplicate = duplicateNode(root);
        while (noDuplicate != null) {
            System.out.print(noDuplicate.val + "-->");
            noDuplicate = noDuplicate.next;
        }
    }

    /**
     * 除去重复元素
     *
     * @param root
     * @return
     */
    private static ListNode duplicateNode(ListNode root) {
        if (root == null) {
            return null;
        }
        ListNode ret = new ListNode(-1);
        ListNode pre = ret;
        ret.next = root;
        while (root != null) {
            while (root != null && root.next != null && root.val == root.next.val) {
                root = root.next;
            }
         //关键代码，下一个节点是不是没有移动
            if (pre.next == root) {
                pre = pre.next;
            } else {
                pre.next = root.next;
            }
            root = root.next;
        }
        return ret.next;
    }
}
  • 两个链表求和，右移求和
package com.xiyu.sentinel.al.linkedlist;

/**
 * 两个数求和右移进位
 *
 * @author yuxi
 */
public class TwoSumRight {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(7, new ListNode(9, null))));
        ListNode head2 = new ListNode(1, new ListNode(7, new ListNode(9, null)));
        ListNode ret = addTwoSumRight(head1, head2);
        while (ret != null) {
            System.out.print(ret.val + "===>");
            ret = ret.next;
        }
    }

    /**
     * @param head1
     * @param head2
     */
    private static ListNode addTwoSumRight(ListNode head1, ListNode head2) {
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        ListNode root = new ListNode(-1, null);
        ListNode deal = root;
        int index = 0;
        while (head1 != null || head2 != null) {
            int val1 = 0;
            if (head1 != null) {
                val1 = head1.val;
                head1 = head1.next;
            }
            int val2 = 0;
            if (head2 != null) {
                val2 = head2.val;
                head2 = head2.next;
            }
            int sum = val1 + val2 + index;
            deal.next = new ListNode(sum % 10, null);
            index = (sum) / 10;
            deal = deal.next;
        }
        if (index != 0) {
            deal.next = new ListNode(index, null);
        }

        return root.next.val == 0 ? root.next.next : root.next;
    }
}
  • 两个链表求和，左移求和
package com.xiyu.sentinel.al.linkedlist;

import java.util.Stack;

/**
 * 链表中两个数求和左移进位
 *
 * @author yuxi
 */
public class TwoSumLeft {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(7, new ListNode(9, null))));
        ListNode head2 = new ListNode(9, new ListNode(7, new ListNode(9, new ListNode(9, null))));
        ListNode ret = addTwoSumLeft(head1, head2);
        while (ret != null) {
            System.out.print(ret.val + "===>");
            ret = ret.next;
        }
    }

    /**
     * 左移求和
     *
     * @param head1
     * @param head2
     * @return
     */
    private static ListNode addTwoSumLeft(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while (head1 != null) {
            ListNode tmp = head1;
            head1 = head1.next;
            tmp.next = null;
            s1.push(tmp);
        }

        while (head2 != null) {
            ListNode tmp = head2;
            head2 = head2.next;
            tmp.next = null;
            s2.push(tmp);
        }
        ListNode root = new ListNode(-1, null);
        int index = 0;
        while (!s1.empty() || !s2.empty()) {
            int val1 = 0;
            if (!s1.empty()) {
                val1 = s1.pop().val;
            }
            int val2 = 0;
            if (!s2.empty()) {
                val2 = s2.pop().val;
            }
            int sum = val1 + val2 + index;
            ListNode cur = new ListNode(sum % 10, null);
            index = sum / 10;
            cur.next = root.next;
            root.next = cur;
        }
        if (index != 0) {
            ListNode cur = new ListNode(index, null);
            cur.next = root.next;
            root.next = cur;
        }
        return root.next.val == 0 ? root.next.next : root.next;

    }
}
  • 求链表的中间节点
package com.xiyu.sentinel.al.linkedlist;

/**
 * 找到链表的中间节点
 *
 * @author yuxi
 */
public class FindMiddle {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        ListNode ret = findMiddle(head);
        System.out.println(ret.val);
    }

    /**
     * 找到中间节点
     *
     * @param head
     * @return
     */
    private static ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;

    }
}
  • 判断链表是否有环
package com.xiyu.sentinel.al.linkedlist;

/**
 * 判断链表是否有环
 *
 * @author yuxi
 */
public class CircleNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        Boolean isCircle = isCircle(head);
        System.out.println(isCircle);
    }

    /**
     * 判断链表是否有环
     *
     * @param head
     * @return
     */
    private static Boolean isCircle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
             slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }

        return false;
    }
}
  • 判断链表是否有环，求环的起始位置
package com.xiyu.sentinel.al.linkedlist;

/**
 * 判断链表是否有环
 *
 * @author yuxi
 */
public class CircleNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        Boolean isCircle = isCircle(head);
        System.out.println(isCircle);
    }

    /**
     * 判断链表是否有环
     *
     * @param head
     * @return
     */
    private static Boolean isCircle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}
  • 链表的插入排序
package com.xiyu.sentinel.al.linkedlist;

/**
 * 链表的插入排序
 *
 * @author yuxi
 */
public class InsertNodeSort {
    public static void main(String[] args) {
        ListNode head = new ListNode(11, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        ListNode ret = insertSort(head);
        while (ret != null) {
            System.out.print(ret.val + "-->");
            ret = ret.next;
        }
    }

    /**
     * 插入排序
     *
     * @param head
     * @return
     */
    private static ListNode insertSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pHelp = new ListNode(-1);
        ListNode cur = head;
        ListNode pre = pHelp;
        ListNode next;
        while (cur != null) {
            next = cur.next;
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            cur.next = pre.next;
            pre.next = cur;
            pre = pHelp;
            cur = next;
        }
        return pHelp.next;
    }
}
  • 链表ReOrder
package com.xiyu.sentinel.al.linkedlist;

/**
 * 链表L0→Ln→L1→Ln-1→L2→Ln-2→
 *
 * @author yuxi
 */
public class ReorderNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(11, new ListNode(2, new ListNode(2,
            new ListNode(3, new ListNode(4, new ListNode(4, null))))));
        reorderList(head);
        while (head != null) {
            System.out.print(head.val + "-->");
            head = head.next;
        }
    }

    /**
     * reorder
     *
     * @param head
     */
    public static void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }

        ListNode cur = head;
        while (cur != null && cur.next != null && cur.next.next != null) {
            ListNode tmp = cur;
            cur = cur.next;
            ListNode preTail = tmp;
            ListNode tail = tmp;
            while (tail != null && tail.next != null) {
                preTail = tail;
                tail = tail.next;
            }
            preTail.next.next = tmp.next;
            tmp.next = preTail.next;
            preTail.next = null;

        }
    }
}

相关文章

  • 链表问题汇总

    写在前面 记录常见的链表操作，基本可以秒杀一切面试题(虽然这不是我们的本意)。这些问题都来源于LeetCode，我...

  • 链表常见问题汇总

    1.给一个单链表，判断其中是否有环的存在；两个指针同时从头指针开始遍历链表，一个每次遍历一个，另外一个每次遍历两个...

  • ROC-AUC 曲线以及PRC曲线

    目录：机器学习常见面试问题汇总问题汇总（1）：逻辑回归问题汇总（2）：支持向量机问题汇总（3）：树模型问题汇总（4...

  • 1.数据结构-链表问题

    链表相关问题 删除节点 链表去重 有环链表 反转链表 链表排序 链表相交 其他问题 面试题 02.03. 删除中间...

  • 单链表的冒泡，快排，选择，插入，归并等多图详解

    上节介绍了链表的基本操作史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)这节介绍链表的5种排序算法...

  • 3.链表（三）

    题目汇总https://leetcode-cn.com/tag/linked-list/206. 反转链表简单[✔...

  • leetcode刷题-链表

    链表题目汇总： 主要是发现 206 141环形链表（快慢指针） 21写递归 19 876 快慢指针，一个走2步，一...

  • 问题汇总（5）：神经网络

    这篇应当也是很重要的把~ 目录：机器学习常见面试问题汇总问题汇总（1）：逻辑回归问题汇总（2）：支持向量机问题汇总...

  • 2.链表（二）

    题目汇总https://leetcode-cn.com/tag/linked-list/92. 反转链表 II中等...

  • 4.链表（四）

    题目汇总https://leetcode-cn.com/tag/linked-list/725. 分隔链表中等（有...

网友评论

    本文标题：链表问题汇总

    本文链接：https://www.haomeiwen.com/subject/rmzdcqtx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    数据结构和算法

    关于我们|服务条款|联系我们|链表问题汇总|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！