第五天——双指针

876.链表的中间节点

给定一个头结点为 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        ListNode temp = head;
        int i=0;

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

        for(int j=1; j<(i/2)+1; j++)
        {
            head = head.next;
        }

        return head;
    }
}

我觉得我这个思路算比较简单暴力的

直接遍历一遍到底,然后取中间值返回

So这里就补充一下官方题解的双指针法

slow一次走一步,fast一次走两步

这样就能在fast到终点时slow正好停在中间

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public 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;
    }
}

19. 删除链表的倒数第 N 个结点

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

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode preNode = null;

        while(fast.next!=null)
        {
            if(n!=0)
            {
                n = n-1;
            }
            if(n==0)
            {
                preNode = slow;
                slow = slow.next;
            }
            fast = fast.next;
        }

        if(preNode == null)
        {
            head = slow.next;
        }
        else
        {
            preNode.next = slow.next;
        }

        return head;
    }
}

我原本的思路其实已经很接近了

快指针先走n步,慢指针再开始走

等到快指针到了的时候慢指针刚好到指定位置

因为这是无头指针所以我就想能不能刚好走到前一位

结果当长度为1 n为1和长度为2 n为2的时候犯了难

正确的思路应该是出了快指针和慢指针还有一个preSlow

也就是慢指针的前一个

走完后根据这个preSlow来进行删除的操作

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注