＜java＞leetcode.适合集中处理的几道链表题

文章目录

一.🚩反转链表

🌎🌎思路演示

🌎🌎代码实现

classSolution{publicListNodereverseList(ListNode head){ListNode prev=head;//排除链表没有节点元素的情况if(head==null){returnnull;}//链表只有一个节点的时候直接反回这个节点if(head.next==null){return head;}ListNode cur=prev.next;ListNode newhead=null;while(cur!=null){ListNode curNext=cur.next;//确保cur已经遍历到最后一个节点了if(curNext==null){
               newhead=cur;}
           cur.next=prev;
           prev=cur;
           cur=curNext;}
        head.next=null;return newhead;}}

大家也来试试吧👏👏：题目链接（反转链表：电脑打开）

二.🌟查找并返回链表的中间节点

🌎方法：快慢指针

🌟🌟定义快指针fast,慢指针slow,让fast和slow从同一个起点开始出发。fast一次走两步，slow一次走一步，当fast走到最后一个节点的时候，slow刚好处于中间节点（fast比slow多走了一半的路程）

🌎🌎代码实现：

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

大家也来试试吧👏👏：查找链表中间节点（电脑打开）

三、删除链表中等于给定值 val 的所有节点

🌎🌎思路演示：

🌎🌎代码展示：

classSolution{publicListNoderemoveElements(ListNode head,int val){//排除空链表if(head==null){returnnull;}ListNode prev=head;ListNode cur=prev.next;while(cur!=null){if(cur.val==val){
                prev.next=cur.next;}else{//驱动双指针进行
                prev=cur;}//驱动双指针进行
            cur=cur.next;}//排除要删除的节点正好是头节点if(head.val==val){
            head=head.next;}return head;}}

大家也来试试吧👏👏:删除指定元素的所有节点

四.链表中倒数第k个结点

思路解析（双指针）： 快慢指针从同意起点，快指针先走k-1步，此时加上fast本身。fast和slow相差k个节点，此时fast与slow同步一步一步向后走。当fast走到最后一个节点，slow恰好在倒数第k个节点

🌎🌎代码展示：

classSolution{publicListNodegetKthFromEnd(ListNode head,int k){ListNode fast=head;ListNode slow=head;while(k-1>0){
            fast=fast.next;
            k--;}while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;}return slow;}}

大家也来试试吧👏👏：链表中倒数第k个结点

五.合并两个有序链表

🌎🌎代码展示：

classSolution{publicListNodemergeTwoLists(ListNode list1,ListNode list2){//创建虚拟头节点ListNode head=newListNode(-1);//定义node遍历新的头结点ListNode node=head;while(list1!=null&&list2!=null){if(list1.val<list2.val){
            node.next=list1;
            list1=list1.next;}else{
            node.next=list2;
            list2=list2.next;}
        node=node.next;}//如果list1是空链表，直接连接list2if(list1==null){
            node.next = list2;}else{
            node.next = list1;}//返回虚拟节点下一个节点return head.next;}}

大家也来试试吧👏👏：合并链表

六.以给定值x为基准将链表分割成两部分

🌎🌎思路叙述：
新建两个链表 sml_dummy , big_dummy ，分别用于添加所有「节点值 <x 」、「节点值 ≥x 」的节点。
遍历链表 head 并依次比较各节点值 head.val 和 x 的大小：

若 head.val < x ，则将节点 head 添加至链表 sml_dummy 最后面；
若 head.val >= x ，则将节点 head 添加至链表 big_dummy 最后面；

遍历完成后，拼接 sml_dummy 和 big_dummy 链表。
最终返回头节点 sml_dummy.next 即可

lass Solution{publicListNodepartition(ListNode head,int x){ListNode smlDummy =newListNode(0), bigDummy =newListNode(0);ListNode sml = smlDummy, big = bigDummy;while(head !=null){if(head.val < x){
                sml.next = head;
                sml = sml.next;}else{
                big.next = head;
                big = big.next;}
            head = head.next;}
        sml.next = bigDummy.next;
        big.next =null;return smlDummy.next;}}

大家也来试试吧👏👏：分割链表

七.删除链表重复节点

publicNodedeleteDuplication(){Node newHead=newNode(-1);Node cur=this.head;Node temp=newHead;while(cur!=null){if(cur.next!=null&&cur.date==cur.next.date){while(cur.next!=null&&cur.date==cur.next.date){
                    cur = cur.next;}
                cur=cur.next;}else{
                temp.next=cur;
                temp=temp.next;
                cur=cur.next;}}
        temp.next=null;return newHead.next;

八.判断回文链表

/**
     *1.找到中间链表
     * 2.反转中间链表以后的节点
     * 3.链表前后对向移动，看最后相遇情况
     * @return
     */publicbooleanchkPalindrome(){if(this.head==null){returnfalse;}if(this.head.next==null){returntrue;}Node fast=this.head;Node slow=this.head;while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;}Node cur = slow.next;while(cur!=null){Node curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;}while(this.head!=slow){if(this.head.date!=slow.date){returnfalse;}if(this.head.next==slow){returntrue;}this.head=this.head.next;
            slow=slow.next;}returntrue;

大家也来试试吧👏👏回文链表

九.输入两个链表，找出它们的第一个公共结点

publicclassSolution{publicListNodegetIntersectionNode(ListNode headA,ListNode headB){if(headA ==null|| headB ==null)returnnull;ListNode pA = headA, pB = headB;while(pA != pB){
        pA = pA ==null? headB : pA.next;
        pB = pB ==null? headA : pB.next;}return pA;}}

大家也来试试吧👏👏相交链表

十.判断链表是否有环

publicclassSolution{publicbooleanhasCycle(ListNode head){ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){
             fast=fast.next.next;
             slow=slow.next;if(fast==slow){returntrue;}}returnfalse;}}

大家也来试试吧👏👏环形链表

十一.返回链表开始入环的第一个节点

publicclassSolution{publicListNodedetectCycle(ListNode head){ListNode fast=head;ListNode slow=head;while(fast!=null&&fast.next!=null){
             fast=fast.next.next;
             slow=slow.next;if(fast==slow){break;}}if(fast==null||fast.next==null){returnnull;}
         slow=head;while(fast!=slow){
             fast=fast.next;
             slow=slow.next;}return fast;}}

大家也来试试吧👏👏142. 环形链表 II