【代码随想录刷题】Day04 链表

1.[24]两两交换链表中的结点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
需要注意的是，不能只是单纯地改变结点内部的值，而是需要实际的进行节点交换

建议使用虚拟头结点进行操作

• 整体操作图：
  
• 操作完之后:
  

这个代码在Leetcode上提交显示超出时间限制

//两两交换链表中的结点
    public ListNode swapPairs(ListNode head){
        ListNode dummyHead=new ListNode(0);//设置虚拟头结点
        dummyHead.next=head;
        ListNode curNode=dummyHead;
        //假设链表是cur->1->2->3->4->5
        ListNode temp= curNode.next;//临时结点，保存1这个节点
        ListNode temp1=curNode.next.next.next;//临时结点，保存3这个节点

        while (curNode.next!=null && curNode.next.next!=null){
            //将2与1调换
            //步骤一：
            curNode.next=curNode.next.next;//cur->2
            //步骤二：
            curNode.next.next=temp;//cur->2->1
            curNode.next.next.next=temp1;//cur->2->1->3
            curNode=curNode.next.next;//cur移动两位，准备下一轮交换，此时cur指向3这个节点

        }
        return dummyHead.next;

    }  

• 进行改进
• • 时间复杂度：O(n)

 //两两交换链表中的结点------优化
    public ListNode swapPairs1(ListNode head){
        ListNode dummyHead=new ListNode(0);//设置虚拟头结点
        dummyHead.next=head;
        ListNode curNode=dummyHead;
        //假设链表是cur->1->2->3->4->5
        ListNode temp;//保存两个结点后面的结点，也就是保存3这个节点
        ListNode firstNode;//保存两个节点中的第一个结点，也就是保存1这个节点
        ListNode secondNode;//保存两个节点中的第二个 结点，也就是2这个节点

        while (curNode.next!=null && curNode.next.next!=null){
            temp=curNode.next.next.next;//保存两个结点后面的结点，也就是保存3这个节点
            firstNode=curNode.next;//保存两个节点中的第一个结点，也就是保存1这个节点
            secondNode=curNode.next.next;//保存两个节点中的第二个 结点，也就是2这个节点
            //将2与1调换
            //步骤一：
            curNode.next=secondNode;//cur->2
            //步骤二：
            secondNode.next=firstNode;//cur->2->1
            firstNode.next=temp;//cur->2->1->3
            curNode=firstNode;//cur移动两位，准备下一轮交换，此时cur指向3这个节点

        }
        return dummyHead.next;
    }

2.[19] 删除链表中的倒数第N个结点

思路：

• 使用双指针法
• 要想删除倒数第N个结点，让快指针指向末尾，同时慢指针指向要删除元素的前一个元素
• 那么，快慢指针只要相差n个结点即可（可以自己画图试一下，比较清楚）
• 这里还是要用到虚拟头结点的，操作起来比较方便

例如：n=2，删除倒数第2个，也就是删除元素3

• 首先让快指针移动2步，此时fast指向 2
• 快慢指针同时移动
• 当fast指向4时，slow指向2（也就是3的前一个元素）
• 进行删除操作

public ListNode removeNthFromEnd(ListNode head,int n){
        //设置虚拟头结点
        ListNode dummyHead=new ListNode(0);
        dummyHead.next=head;

        //快慢指针
        ListNode fastIndex=dummyHead;
        ListNode slowIndex=dummyHead;

        //只要快慢指针相差n个结点即可  先让快指针向前移动n步
        for (int i=0;i<n;i++){
            fastIndex=fastIndex.next;
        }
        //快指针向前移动n步后，快慢指针同时移动
        while (fastIndex.next!=null){
            fastIndex=fastIndex.next;
            slowIndex=slowIndex.next;
        }

        //此时慢指针的位置就是待删除元素的前一个位置
        slowIndex.next=slowIndex.next.next;//删除操作
        return dummyHead.next;
    }

3.[142] 环形链表II （这个需再消化消化）

• 快慢指针法
  讲解视频：

/**
     *  环形链表II
     *  返回链表开始入环的第一个节点
     */
    public ListNode detectCycle(ListNode head){
        ListNode slow=head;
        ListNode fast=head;

        while (fast!=null && fast.next!=null){
            slow=slow.next;//slow走一步
            fast=fast.next.next;//fast走两步
            if (fast==slow){//有环
                ListNode index1=fast;
                ListNode index2=head;
                //两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2){
                    index1=index1.next;
                    index2=index2.next;
                }
                return index1;
            }
        }
        return null;
    }