当前位置：网站首页>Classic linked list OJ strong training problem - fast and slow double pointer efficient solution

Classic linked list OJ strong training problem - fast and slow double pointer efficient solution

2022-07-31 02:19:00 【Chen Yikang】

链表分割

链表回文结构

链表分割

思路：
创建两个链表（A,B）：Create two head and tail pointer positions respectivelynull
创建一个curThe pointer traverses the linked list given by the title
将结点值小于xtail insertionA中,否则插入B中
判断若A段为空,返回BSection header node
为了防止死循环,若B段存在,则有可能BThe last node of the segment is not empty,若不为空,is set to empty
用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段存在,那么有可能bThe last node of the segment is not empty
        if(bs != null){
            be.next = null;
        }
        ae.next = bs;
        return as;
    }
}

链表回文结构

思路：
创建快慢指针
Traverse the linked list through fast and slow pointers
from slow pointersnextStart reversing the second half of the linked list
Finally use two pointers,Determine whether the linked list is a palindrome from the beginning and the end respectively

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if(head == null){
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;   //Pay attention to the order of the fast and slow pointers,Otherwise it will cause rightnull指针的解引用操作
        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;
    }
}

合并两个有序链表

思路：
创建一个虚拟结点
Compare two nodes from scratchvalue值,Connect the smaller value to the dummy node
If a node is empty,Just point the node to another node
Returns the next reception of the virtual node

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;
    }
}

相交链表

思路：
Traverse with two pointers respectivelyA,Btwo linked list,求出长度
Find the difference in length,因为是Y性,All identical nodes follow the same length
求出差值后,Let the long walk through this difference,Both go at the same time
Finally, judge if the two pointers are equal,Returns equal nodes

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性,All identical nodes follow the same length,So find the difference,Let the long walk through this difference,Both go at the same time
            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;
            }*/ //Judgment or not does not matter,Because it will return empty in the end
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}

移除链表元素

思路：
创建两个指针
一个为cur用来遍历链表,Find out which element to remove
另一个为dp指向cur上一个结点
dp的next指向cur的next结点,同时使cur指向下一个结点,To achieve the purpose of deleting multiple nodes

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;//In fact, there is no need to find the previous node here,直接插入结点,交换值即可
                cur = dp.next;
            } else {
                dp = cur;
                cur = cur.next;
            }
        }
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

反转链表

思路
创建一个cur指针,指向头结点的next
Leave the head node blank,as the reversed tail node
创建一个curNext指针,Let him always pointcur的next
让将headpointer ascurThe previous node is used,将headThe address of the node is assigned tocur的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;
    }
}

链表的中间结点

思路：
It is enough to traverse the linked list through fast and slow pointers
fast指向null或者fast.next指向null的时候停下,At this point, the slow pointer is the intermediate node

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个结点

思路：
创建快慢指针
让快指针先走K-1步
Let the fast pointer and the slow pointer move back step by step at the same time
fast指向空时,slowThe pointer points to the penultimateK个元素

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;
    }
}