Day09——链表专题

ゝ一世哀愁。 2024-04-03 12:53 49阅读 0赞

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

*   *   *  18.删除链表的倒数第N个节点
         *  19.链表相交

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

#### 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){
        //因为删除某个节点，需要知道这个节点的上一个节点，fastIndex要执行n+1步的位置。
                fastIndex = fastIndex.next;//快指针后移
                slowIndex = slowIndex.next;//慢指针后移
            }
            slowIndex.next = slowIndex.next.next;//删除第n个节点
            return dummmyNode.next;//返回头节点
        }
    }

#### 19.链表相交 ####

**1.假定链表相交:**

两个指针分别走a+b+c步一定会相遇，即遍历完本链表后，继续遍历另一个链表，直到最后两者相遇，相遇节点为题目的两个链表相交的起始节点。如下图所示

![image-20221015190314251][]

**2.链表不相交**

![image-20221015191139503][]

a,b 分别代表两个链表的长度，则两个指针分别走 a+b+c步后都变成 null，这里c等于0，因为两个链表没有相交的节点。

\*\*注意：\*\*交点不是数值相等，而是指针相等。

**代码实现：**

public class Solution {
        
       public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            ListNode curA = headA;//定义指针curA指向headA
            ListNode curB = headB;//定义指针curB指向headB
            while(curA != curB){
        //当指针不等时
                if(curA==null) curA = headB;//判断curA是否指向空，指向空则指向另一个链表的头节点。
                else curA = curA.next;//不指向空则继续后移。
                
                if(curB==null) curB = headA;//判断curB是否指向空，指向空则指向另一个链表的头节点。
                else curB = curB.next;//不指向空则继续后移。
            }
            return curA;
        }
    }

[image-20221015190314251]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b8b3568600e04f4b94c132e7a274e4b3.png
[image-20221015191139503]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e78a6568167f455587b03a05b657b3f0.png