leetcode双指针（基础）

深碍√TFBOYSˉ_ 2022-09-04 06:47 149阅读 0赞

189.旋转数组  
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。（不使用额外空间）  
输入: nums = \[1,2,3,4,5,6,7\], k = 3  
输出: \[5,6,7,1,2,3,4\]

先将整体数组内容反转，之后前k个反转，以及k之后的内容在反转。  
反转采用双指针实现，k应当根据长度求余数，存在k大于length的情况。

class Solution {
        
        public void rotate(int[] nums, int k) {
        
            k %= nums.length;
            reverse(nums, 0, nums.length - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.length - 1);
        }
    
        public void reverse(int[] nums, int start, int end) {
        
            while (start < end) {
        
                int temp = nums[start];
                nums[start] = nums[end];
                nums[end] = temp;
                start += 1;
                end -= 1;
            }
        }
    }

283移动零  
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: \[0,1,0,3,12\]  
输出: \[1,3,12,0,0\]

说明:

必须在原数组上操作，不能拷贝额外的数组。
    尽量减少操作次数。

两个指针都从左侧出发，快指针找到一个非零数，与慢指针交换，之后慢指针向后移动一格，这样保证慢指针的左侧都为非零且有序，快指针继续向后找非零的数。  
错误思路：两个指针一个找0，一个找非0，找到就交换，\[0,1,1\]无法实现效果，故错误。

class Solution {
        
        public void moveZeroes(int[] nums) {
        
            int n = nums.length, left = 0, right = 0;
            while (right < n) {
        
                if (nums[right] != 0) {
        
                    swap(nums, left, right);
                    left++;
                }
                right++;
            }
        }
    
        public void swap(int[] nums, int left, int right) {
        
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }

1.  链表的中间结点

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

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

快指针一次走两格，慢指针走一格，快指针走到结尾时，慢指针即为结果。

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

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

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

进阶：你能尝试使用一趟扫描实现吗？

快指针先走n格，之后慢指针再出发，快指针走完之后，慢指针所指的就是要删除的后继，所以，慢指针要从头节点的前一个开始，保证只遍历一次。（申请一个节点指向头节点）

class Solution {
        
        public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummy = new ListNode(0, head);
            ListNode first = head;
            ListNode second = dummy;
            for (int i = 0; i < n; ++i) {
        
                first = first.next;
            }
            while (first != null) {
        
                first = first.next;
                second = second.next;
            }
            second.next = second.next.next;
            ListNode ans = dummy.next;
            return ans;
        }
    }