栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

<java>leetcode.适合集中处理的几道链表题

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

<java>leetcode.适合集中处理的几道链表题

文章目录
  • 一.反转链表
  • 二.查找并返回链表的中间节点
  • 三、删除链表中等于给定值 val 的所有节点
  • 四.链表中倒数第k个结点
  • 五.合并两个有序链表
  • 六.以给定值x为基准将链表分割成两部分
  • 七.删除链表重复节点
  • 八.判断回文链表
  • 九.输入两个链表,找出它们的第一个公共结点
  • 十.判断链表是否有环
  • 十一.返回链表开始入环的第一个节点


一.反转链表

思路演示

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev=head;
        //排除链表没有节点元素的情况
        if(head==null)
        {
            return null;
        }
        //链表只有一个节点的时候直接反回这个节点
        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多走了一半的路程)


代码实现:

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

    }
}

大家也来试试吧:查找链表中间节点(电脑打开)

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


思路演示:

代码展示:

class Solution {
    public ListNode removeElements(ListNode head, int val) {
    //排除空链表
        if(head==null)
        {
            return null;
        }
    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个节点

代码展示:

class Solution {
    public ListNode getKthFromEnd(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个结点

五.合并两个有序链表

代码展示:

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

大家也来试试吧:合并链表

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

思路叙述:
新建两个链表 sml_dummy , big_dummy ,分别用于添加所有「节点值 遍历链表 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 {
    public ListNode partition(ListNode head, int x) {
        ListNode smlDummy = new ListNode(0), bigDummy = new ListNode(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;
    }
}

大家也来试试吧:分割链表

七.删除链表重复节点

 public Node deleteDuplication()
    {
       Node newHead=new Node(-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;

八.判断回文链表

 
    public boolean chkPalindrome()
    {
        if (this.head==null)
        {
            return false;
        }
        if (this.head.next==null)
        {
            return true;
        }
        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)
            {
                return false;
            }
            if (this.head.next==slow)
            {
                return true;
            }
            this.head=this.head.next;
            slow=slow.next;
        }

        return true;



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

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

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;

    }
}

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

十.判断链表是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast=head;
         ListNode slow=head;
         while (fast!=null&&fast.next!=null)
         {
             fast=fast.next.next;
             slow=slow.next;
             if (fast==slow) {
                 return true;
             }
         }
         return false;
    }
}

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

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

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) {
                 break;
             }
         }
         if (fast==null||fast.next==null)
         {
             return null;
         }
         slow=head;
         while (fast!=slow)
         {
             fast=fast.next;
             slow=slow.next;
         }
         return fast;
    }
}

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

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/977711.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号