Leetcode 链表简单题

本文阅读 6 分钟
首页 代码,Java 正文

题目链接 21.合并两个有序链表 img 思路: 题目已经说明了给出的两个链表,A,B都是有序的,为了使得他们合并后的链表也是有序的,我们先定义一个新的链表C的头结点,我们应该定义两个指针,分别指向A链表的头结点,和B链表的头结点,对链表进行遍历,如果A链表的元素值比较小,则让C链表的头结点指向A,让后让A的指针后移,如果B链表指向的元素小,也是进行同样的操作。

注意:刚开始链表循环的条件是两个链表都非空,循环结束则说明有一个链表为空,当时我们不知道是哪一个链表为空,所以要进行判断,如果A链表为空,则让C链表的当前结点指向B链表

class Solution { 
    public ListNode mergeTwoLists(ListNode p, ListNode q) { 
            
            ListNode node=new ListNode();
            ListNode head=node;
             
            while(p!=null && q!=null){ 
                if(p.val < q.val){ 
                    node.next=p;
                    p=p.next;
                    node=node.next;

                    
                }else{ 
                    node.next=q;
                    q=q.next;
                    node=node.next;
                }
            }
           node.next= (p!=null)?p:q;
           return head.next;
    }
}

题目链表 141 环形链表 img img

思路:

  • 因为题目要求判断是否成环,那么如果链表为空,或者只有一个结点,都无法成环
  • 我们可以定义快慢指针,快指针移动2次,慢指针移动一次,如果链表成环,最后两个指针肯定可以相遇
/** 使用快慢指针 */
public class Solution { 
    public boolean hasCycle(ListNode head) { 
       if(head == null || head.next==null) return false;
       ListNode slow=head;
       ListNode fast=head.next;
       while(fast!=null && fast.next!=null){ 
           if(slow==fast) return true;
           slow=slow.next;
           fast=fast.next.next;
       }
       return false;
       
    }
}

题目链接: 160 相交链表 img img 思路:

  • 假设A链表未相交部分长度是a,相交部分长度c
  • 假设B链表未相交部分长度是b,相交部分长度是c
  • 我们分别遍历A和B,当A遍历完后,就让A指向B的头结点,B也一样的做法
  • 只要A和B的指针不相等,就不断的遍历,最后一定会相遇
  • 详细的思路大家可以看看官方提供的解题思路: 力扣官方的解题思路
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;

 
    }
}

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 img 思路: 这道题目第一眼看起来虽然简单,但是细节没有注意的话,还是会出错,<font size="4" color="red">我们得考虑特殊情况,如果删除的元素是头结点要怎么办呢? 所以,我们应该先找到头结点所在位置,当头结点非空并且头结点的元素不等于val,就让指针后移,就可以得到头结点</font>

头结点找到后,就很容易写出代码了。

class Solution { 
    public ListNode removeElements(ListNode head, int val) { 
         while(head!=null&&head.val==val){ 
            head=head.next;
        }        
        if(head==null) return head;
        ListNode curr=head;
        while(curr.next!=null){             
            if(curr.next.val==val){                 
                curr.next=curr.next.next;
            }else{ 
                curr=curr.next;
            }
        }
        return head;

    }

题目链接: 206 反转链表 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 img img

思路:

  • 如果头结点为null,或者链表只有一个元素,则直接返回头结点
  • 否则的话,我们定义两个指针,pre表示当前结点的前一个结点,curr表示当前结点
  • 对链表进行遍历,开始反转,指针记得变化
public ListNode reverseList(ListNode head) { 
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) { 
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;

        }
        return pre;
    }

题目链接: 234 回文链表 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 img 一看到这道题目,不知道有没有小伙伴和我一样,心想,不就是先把链表反转,然后和原来的链表进行比较吗,这么简单,那么,恭喜你,和我一样都想错了。 易错点:我们写了函数反转后,由于是引用传递,也就是链表本身会发生变化,所以不能这样做,除非有两个链表,才可以这么写。

思路分析: 我们可以遍历链表,然后把结点的值保存在ArrayList中,然后进行回文判断

class Solution { 
    public boolean isPalindrome(ListNode head) { 
        List list = new ArrayList();
        ListNode p = head;
        while (p != null) { 
            list.add(p.val);
            p = p.next;
        }
        //开始判断 
            for (int i = 0,j=list.size()-1; i <=j; i++,j--) { 
                if (list.get(i)!=list.get(j)){ 
                    return false;
                }
            }
            return true;                
    }     
   
}

题目链接: 剑指 Offer 22. 链表中倒数第k个节点 img

方法1 计算链表长度,根据索引找到结点

  • 先计算出链表长度 思路:
  • 然后根据索引找到对应的结点
class Solution { 
    public ListNode getKthFromEnd(ListNode head, int k) { 
            int len=length(head);
            ListNode p=head;
            int index=len-k;
            int cnt=0;
            while(cnt<index){ 
                p=p.next;
                cnt++;
            }
            return p;
    }
    //获取链表长度
    public int length(ListNode head){ 
        int i=0;
        ListNode p=head;
        while(p!=null){ 
            p=p.next;
            i++;

        }
        return i;
    }
}

方法2 快慢指针

题目要求我们找到的是倒数第k个结点,我们可以让快指针和慢指针指向的结点相差k个,那么当快指针指向链表尾部的空结点的时候,说明慢指针刚好是倒数第k个结点

class Solution { 
    public ListNode getKthFromEnd(ListNode head, int k) { 
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k > 0) { 
            fast = fast.next;
            k--;
        }
        while (fast != null) { 
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

题目链接: 876 链表的中间结点 img

思路:

  • 定义快慢指针
  • 快指针每次移动两个结点
  • 慢指针每次移动一个结点
  • 当快指针指向的是null,此时慢指针指向的就是中间结点
class Solution { 
    public ListNode middleNode(ListNode head) { 
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){ 
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://zengyihong.blog.csdn.net/article/details/124722614
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复