Day18——双指针专题

迷南。 2024-04-01 10:15 98阅读 0赞

#### 文章目录 ####

*   *   *  16.反转链表
         *  17.两两交换链表中的节点
         *  18.删除链表的倒数第N个节点

--------------------

#### 16.反转链表 ####

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，因为开始反转的时候cur->next就改变值了。

接下来，就是循环走如下代码逻辑了，继续向后移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

**指向谁 就等于谁**

**代码实现：**

//双指针
    class Solution {
        
           public ListNode reverseList(ListNode head) {
        
            ListNode pre = null;
            ListNode cur = head;
            ListNode temp = null;
            while (cur!=null){
        
                temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }
    }

// 递归 
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            return reverse(null, head);//将prev置为null，cur置为head
        }
        private ListNode reverse(ListNode prev, ListNode cur) {
        
            if (cur == null) {
        
                return prev;
            }
            ListNode temp = null;
            temp = cur.next;// 先保存下一个节点
            cur.next = prev;// 反转
            // 更新prev、cur位置
            return reverse(cur, temp);// prev = cur; cur = temp;
        }
    }

#### 17.两两交换链表中的节点 ####

1.如下图所示:

先将cur虚拟头节点指向节点2，其次节点2指向节点1，最后节点1指向节点3，**交换链表之前将节点1和节点3用临时节点记录**，之后完成步骤一二三，第一轮交换完成后，**cur往后移动二位，准备下一轮交换**，最后返回cur.next即头节点。

![image-20221014201154519][]

![image-20221014203832850][]

**代码实现：**

//虚拟头节点
    class Solution {
        
     public ListNode swapPairs(ListNode head) {
        
            ListNode dummy = new ListNode(0);//设置一个虚拟头节点
            dummy.next = head;//将虚拟头节点指向head，这样方便后续操作。
            ListNode cur = dummy;//用cur临时指针来代替虚拟头节点
         
            while(cur.next!=null&&cur.next.next!=null){
        //分别排除偶数和奇数
                ListNode temp = cur.next;//记录临时节点
                ListNode temp1 = cur.next.next.next;//记录临时节点
                
                cur.next = cur.next.next;//步骤一
                cur.next.next = temp;//步骤二
                temp.next = temp1;//步骤三
                
                cur = cur.next.next;//cur移动两位，准备下一轮交换
            }
            return dummy.next;//返回头节点
        }
    }

// 递归版本
    class Solution {
        
        public ListNode swapPairs(ListNode head) {
        
            // base case 退出提交
            if(head == null || head.next == null) return head;
            // 获取当前节点的下一个节点
            ListNode next = head.next;
            // 进行递归
            ListNode newNode = swapPairs(next.next);
            // 这里进行交换
            next.next = head;
            head.next = newNode;
            return next;
        }
    }

#### 18.删除链表的倒数第N个节点 ####

**思路：**

1.循环遍历，只要快慢指针相差 n 个结点即可

2.因为删除某个节点，需要知道这个节点的上一个节点，`fastIndex`要执行n+1步的位置来判断，所以`fastIndex.nex`t指向null，循环结束，这时候slow在删除节点的上一个节点，执行删除操作。

**代码实现：**

class Solution {
        
       public ListNode removeNthFromEnd(ListNode head, int n) {
        
            ListNode dummmyNode = new ListNode(0);//创建虚拟头节点
            dummmyNode.next = head;//让虚拟头节点的next指向head
            ListNode fastIndex = dummmyNode;//定义快指针
            ListNode slowIndex = dummmyNode;//定义慢指针
            for(int i = 0;i < n;i++){
        //循环遍历，只要快慢指针相差 n 个结点即可
                fastIndex = fastIndex.next;
            }
            while (fastIndex.next!=null){
        //因为删除某个节点，需要知道这个节点的上一个节点，slow才能指向删除节点的上一个节点
                fastIndex = fastIndex.next;//快指针后移
                slowIndex = slowIndex.next;//慢指针后移
            }
            slowIndex.next = slowIndex.next.next;//删除第n个节点
            return dummmyNode.next;//返回头节点
        }
    }

[image-20221014201154519]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6674e5ced8d549879fc9537018ff3638.png
[image-20221014203832850]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/78d6de4eb43e4332a755f69bbf002d56.png