算法通关村第一关——链表经典问题之双指针笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第一关——链表经典问题之双指针笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

class ListNode{
    public int val;
    public ListNode next;

    ListNode(int x){
        val = x;
        next = null;
    }
}

基本结构

1.寻找中间结点

 /*
    * 使用快慢指针，slow走一步，fast走两步，当fast遇到null时slow到达中间，
    * [1,2,3,4,5,6]有的中间说的是3，有的是4，这里的快慢指针指的是4.
    * */
    public ListNode middleNode(ListNode head){
        ListNode slow = head,fast = head;
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

2.寻找倒数第k个元素

/*
     *本题的思路分析：
     * [1,2,3,4,5,6,7,8,9]
     * 要找倒数第k个元素，slow在头部，fast移动到正数第k个元素，
     * 这时slow与fast中间差着k个元素，然后让slow和fast指针同时向后移动，
     * 保留此区间k，当fast指向末尾的时候，slow指向的就是倒数第k个元素
     *
     * */
    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;
    }

3.旋转链表

算法通关村第一关——链表经典问题之双指针笔记,算法,链表,笔记文章来源地址https://www.toymoban.com/news/detail-628166.html

public ListNode rotateRight(ListNode head,int k){
        if (head == null || k==0) {
            return head;
        }

        ListNode temp = head;
        ListNode fast = head;
        ListNode slow = head;
        int len = 0;

        while (temp != null){
            temp = temp.next;
            len++;
        }

        if (k%len==0){//也可以写k==len
            return temp;
        }

        while ((k%len) >0){
            k--;
            fast = fast.next;
        }

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

        ListNode res = slow.next;
        slow.next = null;
        fast.next = temp;
        return res;
    }

到了这里，关于算法通关村第一关——链表经典问题之双指针笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！