当前位置：网站首页>经典链表OJ强训题——快慢双指针高效解法

经典链表OJ强训题——快慢双指针高效解法

2022-07-31 02:13:00 【陈亦康】

目录

链表分割

链表回文结构

合并两个有序链表

​编辑

相交链表

移除链表元素

反转链表

链表的中间结点

链表中倒数第K个结点

链表分割

 思路：

  1. 创建两个链表（A，B）：分别创建两个头尾指针置null
  2. 创建一个cur的指针遍历题目所给链表
  3. 将结点值小于x的尾插入A中，否则插入B中
  4. 判断若A段为空，返回B段头结点
  5. 为了防止死循环，若B段存在，则有可能B段最后一个结点不为空，若不为空，则置为空
  6. 用A链表的尾结点，连接B链表的头结点
public class Partition {
    public ListNode partition(ListNode head, int x) {
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = head;
        while(cur != null){
            //进a段
            if(cur.val < x){
                //第一次进as
                if(as == null){
                    as = cur;
                    ae = cur;
                }
                else{
                    ae.next = cur;
                    ae = cur;
                }
            }
            else{
                if(bs == null){
                    bs = cur;
                    be = cur;
                }
                else{
                    be.next = cur;
                    be = cur;
                }
            }
            cur = cur.next;
        }
        //如果a段为空
        if(as == null){
            return bs;
        }
        //防止死循环，如果b段存在，那么有可能b段最后一个结点的不为空
        if(bs != null){
            be.next = null;
        }
        ae.next = bs;
        return as;
    }
}

链表回文结构

 思路：

  1. 创建快慢指针
  2. 通过快慢指针遍历链表
  3. 从慢指针的next开始反转后半段链表
  4. 最后用两指针，分别从头尾判断链表是否回文
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;   //快慢指针注意前后顺序，否则会引起对null指针的解引用操作
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }// 1 2  2 1
        //开始反转
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext =cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //判断回文
        cur = head;
        while(cur != slow){
            if(cur.val != slow.val){
                return false;
            }
            if(cur.next == slow){
                return true;
            }
            cur = cur.next;
            slow = slow.next;
        }
        return true;
    }
}

合并两个有序链表

 思路：

  1. 创建一个虚拟结点
  2. 从头开始比较两个结点value值，将较小值连接虚拟结点
  3. 若有一个结点为空时，将该结点指向另一个结点即可
  4. 返回虚拟结点的下一个接待
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }
        if(list1 == null){
            tmp.next = list2;
        }
        else{
            tmp.next = list1;
        }
        return newHead.next;
    }
}

相交链表

 

思路：

  1. 分别用两指针遍历A，B两链表，求出长度

  2. 求长度差值，因为是Y性，所有相同结点后面的长度是一样的

  3. 求出差值后，让长的走完这段差值，两个再同时走

  4. 最后判断如果两指针相等，则返回相等结点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int szA = 0;
        int szB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        //求A链表长度
        while(curA != null){
            curA = curA.next;
            szA++;
        }
        //求B链表长度
        while(curB != null){
            curB = curB.next;
            szB++;
        }
        curA = headA;
        curB = headB;
        if(szA > szB){
            //求差值，因为是Y性，所有相同结点后面的长度是一样的，所以求差值，让长的走完这段差值，两个再同时走
            int diff = szA - szB;
            while(diff != 0){
                curA = curA.next;
                diff--;
            }
        }
        else{
            int diff = szB - szA;
            while(diff != 0){
                curB = curB.next;
                diff--;
            }
        }
        while(curA != curB){
           /* if(curA == null){
                return null;
            }*/ //判不判断无所谓，因为最后都会返回空
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}

移除链表元素

 思路：

  1. 创建两个指针
  2. 一个为cur用来遍历链表，找出要删除的元素
  3. 另一个为dp指向cur上一个结点
  4. dp的next指向cur的next结点，同时使cur指向下一个结点，达到删除多个结点的目的
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null){
            return null;
        }
        ListNode cur = head;
        ListNode dp = cur;
        while(cur != null) {
            if (cur.val == val) {
                dp.next = cur.next;//其实这里可以不用找前一个结点，直接插入结点，交换值即可
                cur = dp.next;
            } else {
                dp = cur;
                cur = cur.next;
            }
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

反转链表

思路 

  1. 创建一个cur指针，指向头结点的next
  2. 将头节点置空，作为反转后的尾结点
  3. 创建一个curNext指针，让他始终指向cur的next
  4. 让将head指针当作cur的上一个结点用，将head的结点的地址赋给cur的next，让cur指向curNext，curNext指向cur的next循环即可
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

链表的中间结点

思路：

  1. 通过快慢指针遍历链表即可
  2. fast指向null或者fast.next指向null的时候停下，此时慢指针便是中间结点 
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

链表中倒数第K个结点

 思路：

  1. 创建快慢指针
  2. 让快指针先走K-1步
  3. 再让快指针和慢指针同时向后一步一步挪动
  4. fast指向空时，slow指针指向的便是倒数第K个元素
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k <= 0 || head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k-1 != 0){
                fast = fast.next;
                if(fast == null){
                    return null;//k过大
                }
                k--;
            }
        while(fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
        return slow;
    }
}

 

原网站

版权声明
本文为[陈亦康]所创，转载请带上原文链接，感谢
https://blog.csdn.net/CYK_byte/article/details/126076587

边栏推荐

猜你喜欢

随机推荐