小工具知识网

当前位置: 首页 > 行业知识 > 算法——链表王

行业知识

算法——链表王

2026-11-16 13:21:48 来源:互联网转载

��表刷题详解

203.移除链表元素

力扣题目链接(opens new window)

题意:删除链表中等于给定值 val 的所有节点。

示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]

示例 2: 输入:head = [], val = 1 输出:[]

示例 3: 输入:head = [7,7,7,7], val = 7 输出:[]

/** * 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 ListNode removeElements(ListNode head, int val) {        ListNode dummy =new ListNode(-1);        dummy.next=head;        ListNode cur =head;        ListNode pre =dummy;        while( cur != null){            if(cur.val ==val){              pre.next=cur.next;            }else{                 pre=cur;            }              cur =cur.next;                            }                return dummy.next;    }}

删除时需要知道前面一个节点和当前节点,如果不等于只需 pre =cur 就可以了,cur =cur.next则是等于不等于都要执行的。

707.设计链表

力扣题目链接(opens new window)

题意:

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。
    class LinkNode{    int val;    LinkNode next;    LinkNode(){}    LinkNode(int val){        this.val =val;    }}class MyLinkedList {    int size;    LinkNode head;    public MyLinkedList() {        size =0;        head = new LinkNode(0);    }        public int get(int index) {       if(indexsize-1) return -1;        LinkNode cur=head.next;            while(index>0){                cur=cur.next;                    index--;            }            return cur.val;    }        public void addAtHead(int val) {        LinkNode newNode = new LinkNode(val);        newNode.next=head.next;        head.next=newNode;        size++;        // LinkNode cur =head.next;        // LinkNode pre =head;        // LinkNode valNode =new LinkNode(val);        // valNode.next=cur;        // pre.next=valNode;        // size++;    }        public void addAtTail(int val) {        LinkNode tmp = head;        LinkNode newNode =new LinkNode(val);        while(tmp.next !=null){            tmp=tmp.next;        }        tmp.next=newNode;        newNode.next=null;        size++;    }        public void addAtIndex(int index, int val) {         if (index > size) {            return;        }        if (index 0){            pre=pre.next;            cur=cur.next;            index--;        }        newNode.next= cur;        pre.next= newNode;        size++;    }        public void deleteAtIndex(int index) {        if (index = size) {            return;        }        LinkNode pre = head;        LinkNode cur = head.next;        while(index>0){            index--;            pre= pre.next;            cur=cur.next;        }        pre.next=cur.next;        size--;    }}

    PS:要学会定义链表

    206.反转链表

    力扣题目链接(opens new window)

    题意:反转一个单链表。

    示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    /** * 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 ListNode reverseList(ListNode head) {        ListNode pre =null;        ListNode cur =head;         ListNode tmp;        while(cur !=null){            tmp =cur.next;            cur.next= pre;            pre =cur ;            cur =tmp;        }        return pre;    }}

    PS:无需虚拟头结点,直接操作即可,需要一个tmp来保存当前的下一个节点,本来null在最后面,反转后要在最前面

    24. 两两交换链表中的节点

    力扣题目链接(opens new window)

    给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

    /** * 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 ListNode swapPairs(ListNode head) {        ListNode dummy = new ListNode(-1,head);        ListNode cur =dummy;        ListNode firstNode ;        ListNode secondNode ;        ListNode tmp;        while(cur.next!=null && cur.next.next !=null){            tmp =cur.next.next.next;           firstNode =cur.next;           secondNode = cur.next.next;                     cur.next= secondNode;           secondNode.next=firstNode;           firstNode.next=tmp;           cur=firstNode;         }        return dummy.next;    }}

    PS:做这种交换节点最好要画图,这题需要虚拟头结点,和上一题不同的是,这题需要返回第一个节点的值,就是dummy.next,而上一题反转链表后的第一个节点就是NULL.cur=firstNode中因为second和first已经换过位置了,所以相当于cur前进了两个,因为用到了cur.next.next.next;,所以要保证cur.next.next不为null,当然前提是cur.next不为null

    删除链表的倒数第N个节点

    力扣题目链接(opens new window)

    给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

    进阶:你能尝试使用一趟扫描实现吗?

    示例 1:

    输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] 示例 2:

    输入:head = [1], n = 1 输出:[] 示例 3:

    输入:head = [1,2], n = 1 输出:[1]

    /** * 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 ListNode removeNthFromEnd(ListNode head, int n) {        ListNode dummy = new ListNode(-1,head);        ListNode fastNode=dummy;        ListNode slowNode=dummy;        while(n>0){            fastNode=fastNode.next;            n--;        }        fastNode=fastNode.next;        while(fastNode!=null ){            fastNode=fastNode.next;            slowNode=slowNode.next;        }        slowNode.next=slowNode.next.next;         return dummy.next;    }   }

    PS:寻找倒数节点时可以使用双指针的方法

    双指针的经典应用,如果要删除倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。删掉slow所指向的节点就可以了。

    思路是这样的,但要注意一些细节。

    分为如下几步:

    • 首先这里我推荐大家使用虚拟头结点,这样方便处理删除实际头结点的逻辑,如果虚拟头结点不清楚
    • 定义fast指针和slow指针,初始值为虚拟头结点,如图:
      • fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作),如图:
      • fast和slow同时移动,直到fast指向末尾,如题:
      • 删除slow指向的下一个节点,如图:

        面试题 02.07. 链表相交

        同:160.链表相交

        力扣题目链接(opens new window)

        给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

        图示两个链表在节点 c1 开始相交:

        题目数据 保证 整个链式结构中不存在环。

        注意,函数返回结果后,链表必须 保持其原始结构 。

        示例 1:

        示例 2:

        示例 3:

        /** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        ListNode cur1=headA;        ListNode cur2=headB;        int lenA =0;        int lenB =0;        while(cur1!=null){            cur1=cur1.next;            lenA++;        }          while(cur2!=null){            cur2=cur2.next;            lenB++;        }         ListNode tmpA =headA;        ListNode tmpB =headB;        if(lenA>lenB){            int n =lenA -lenB;            while(n>0){                tmpA=tmpA.next;                n--;            }        }else{             int n =lenB -lenA;                       while(n>0){                tmpB=tmpB.next;                n--;            }        }            while(tmpA!=null){                if(tmpA==tmpB) return tmpA;                tmpA=tmpA.next;                tmpB=tmpB.next;                            }                    return null;    }}

        PS:这题较为简单,因为比的是地址,所以不用考虑值相等而非地址相等的情况,可以先分别算出两个链表的长度,让长的链表先移动长度之差的距离,然后再一一判断两个指针是否相等,注意if(tmpAtmpB) return tmpA;要放在一开始就执行,因为公共节点可能是移动后的第一个节点

        142.环形链表II

        力扣题目链接(opens new window)

        题意: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

        为了表示给定链表中的环,使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

        说明:不允许修改给定的链表。

        思路是定义一个快指针移动2个单位,定义一个慢指针每次移动一个单位,如果最后快指针与慢指针相等,则可以判断有环,若最后快指针指向了null,则证明该链表没有环了,接下来判断入环的第一个节点,需要使用数学的方法

        如果有环,如何找到这个环的入口

        此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。

        假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示:

        那么相遇时: slow指针走过的节点数为: x + y, fast指针走过的节点数:x + y + n (y + z),n为fast指针在环内走了n圈才遇到slow指针, (y+z)为 一圈内节点的个数A。

        因为fast指针是一步走两个节点,slow指针一步走一个节点, 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2:

        (x + y) * 2 = x + y + n (y + z)

        两边消掉一个(x+y): x + y = n (y + z)

        因为要找环形的入口,那么要求的是x,因为x表示 头结点到 环形入口节点的的距离。

        所以要求x ,将x单独放在左面:x = n (y + z) - y ,

        再从n(y+z)中提出一个 (y+z)来,整理公式之后为如下公式:x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的,因为 fast指针至少要多走一圈才能相遇slow指针。

        先拿n为1的情况来举例,意味着fast指针在环形里转了一圈之后,就遇到了 slow指针了。

        当 n为1的时候,公式就化解为 x = z,

        这就意味着,从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。

        也就是在相遇节点处,定义一个指针index1,在头结点处定一个指针index2。

        让index1和index2同时移动,每次移动一个节点, 那么他们相遇的地方就是 环形入口的节点。

        动画如下:

        那么 n如果大于1是什么情况呢,就是fast指针在环形转n圈之后才遇到 slow指针。

        其实这种情况和n为1的时候 效果是一样的,一样可以通过这个方法找到 环形的入口节点,只不过,index1 指针在环里 多转了(n-1)圈,然后再遇到index2,相遇点依然是环形的入口节点。

        public class Solution {    public ListNode detectCycle(ListNode head) {        ListNode fast = head;        ListNode slow =head;        while(fast!=null && fast.next !=null){            fast=fast.next.next;            slow=slow.next;            if(fast==slow){                ListNode tmp2 =fast;                ListNode tmp = head;                while(tmp!=tmp2){                    tmp2=tmp2.next;                    tmp= tmp.next;                }                return tmp;            }        }        return null;    }}
          ListNode fast = head;    ListNode slow =head;    while(fast!=null && fast.next !=null){        fast=fast.next.next;        slow=slow.next;        if(fast==slow){            ListNode tmp2 =fast;            ListNode tmp = head;            while(tmp!=tmp2){                tmp2=tmp2.next;                tmp= tmp.next;            }            return tmp;        }    }    return null;}

        }

                                                        

上一篇:易语言关闭进程线程秘籍,深度解析关闭进程中的线程方法

下一篇:服务器怎么注册微信?