代码训练营 DAY4打卡

标签：链表 head ListNode 训练营 current next apointer 打卡 DAY4

本文由GarfieldTheOldCat原创，转载请标明dekkyandlappy-CSDN博客

今天学习了链表的第二课时，链表基础内容在代码训练营 DAY3 打卡

本文由GarfieldTheOldCat原创，转载请标明

两两交换链表中的节点

这道题目的第一个难点在于对题目意思的理解，什么是两两交换？举个例子：

【 A，B，C，D】交换之后是【B，A，D，C】

而【 A，B，C，D，E】交换之后是【B，A，D，C，E】

交换的是整个节点，包括值和指针，而不是仅仅交换节点值；另外，如果是奇数个节点则不交换。

这类题目的思路其实不是很困难：两个指针指向操作的节点后交换，但是实时起来有些值得注意的地方：

引入虚拟头节点Dummyhead，初始化current指针，开始时指向Dummyhead
存储两个节点：temp=current.next；temp1=temp.next.next.next，用于修改节点next属性
current.next=temp.next
current.next.next=temp
temp.next=tem1
current=current.next.next
遍历链表

注意：

循环条件：current.next != null（current为链表末尾，链表节点数为偶数）且 current.next.next != null（current为链表倒数第二个节点，链表节点数为奇数），注意这两个条件的顺序不可以颠倒，否则可能导致空指针异常；
current永远位于需要操作的节点对的前一个

lc24：24. 两两交换链表中的节点

java版本：

第一次的代码运行报超时

// ver1, 运行超时：没有移动 current
    public ListNode swapPairs_0(ListNode head) {
        ListNode Dummyhed=new ListNode( );
        Dummyhed.next=head;
        ListNode current=Dummyhed;
        while( current.next != null && current.next.next !=null){
            ListNode temp = current.next;
            ListNode temp1 = current.next.next.next;

            current.next=temp.next;
            current.next.next=temp;
            temp.next=temp1;
        }
        return Dummyhed.next;
    }

java超时先检查是不是掉进死循环里了，果然，没有移动current导致永远无法退出循环，修正后代码即可通过：

// ver2

    public ListNode swapPairs(ListNode head) {
        ListNode Dummyhed=new ListNode( );
        Dummyhed.next=head;
        ListNode current=Dummyhed;
        while( current.next != null && current.next.next !=null){
            ListNode temp = current.next;
            ListNode temp1 = current.next.next.next;

            current.next=temp.next;
            current.next.next=temp;
            temp.next=temp1;
            current=current.next.next;
        }
        return Dummyhed.next;
    }

python版本

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        Dummyhead = ListNode()
        Dummyhead.next = head
        current = Dummyhead
        while (current.next is not None) and (current.next.next is not None):
            temp = current.next
            temp1 = current.next.next.next

            current.next = temp.next
            current.next.next = temp
            temp.next = temp1
            current = temp

        return Dummyhead.next

TODO：实际上这道题可以用递归做，但是我对递归的理解还不够，过段时间再回来试试。

删除链表的第n个节点

首先想到的是遍历两次的暴力解法，但是这类题目靠双指针可以做到只要遍历一次就可以删除。

这道问题的核心是找到需要删除的节点（确切的说，是需要删除的节点的前一个节点以完成操作），因此，我们只需要两枚间距为n+1的指针，当右侧的指针完成遍历指向null时，左侧指针将刚好到达删除的节点的前一个节点。

为了简化代码，引入虚拟头节点以应对删除第一个节点的情况。

lc19：19. 删除链表的倒数第 N 个结点

java

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode Dummyhead=new ListNode();
        Dummyhead.next=head;

        ListNode fast=Dummyhead;
        ListNode slow =Dummyhead;
        n++;
        // 移动快指针
        while(n-->0 && fast != null){
            fast= fast.next;
        }
        while( fast != null){
            slow=slow.next;
            fast=fast.next;
        }
        slow.next=slow.next.next;
        return Dummyhead.next;
    }

python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        Dummyhead= ListNode()
        Dummyhead.next=head
        fast=Dummyhead
        slow=Dummyhead

        n=n+1
        while(n>0) and (fast is not None):
            fast=fast.next
            n=n-1

        while fast is not None:
            fast=fast.next
            slow=slow.next

        slow.next =slow.next.next
        return Dummyhead.next

理解思路以后实现起来还是比较容易的。

链表相交

由链表定义，若两个链表有交点，则从交点起，两个链表的对应节点会完全相同。因此，我们只需要将两个链表的末尾对齐，从较短的链表的头节点开始寻找两个两个链表对应相同的节点即可。

步骤如下：

遍历两个链表，统计长度alength和blength
为了方便操作，如果b链表更长，则将其与a链表交换
求得两个链表的长度差delta
移动a链表指针apointer到第delta个节点，bpointer到headB，对其两个链表
遍历两个链表剩余部分，寻找相同节点。

面试题02.07：面试题 02.07. 链表相交

java版本：

public ListNode getIntersectionNode_1(ListNode headA, ListNode headB) {
        ListNode apointer = headA;
        int alength=0;
        while(apointer != null){
            alength++;
            apointer=apointer.next;
        }
        ListNode bpointer = headB;
        int blength=0;
        while(bpointer != null){
            blength++;
            bpointer=bpointer.next;
        }

        if (alength < blength){
            ListNode temp =headA;
            headA=headB;
            headB=temp;
            int tempint=alength;
            alength=blength;
            blength=tempint;
        }
        apointer=headA;
        bpointer=headB;

        int delta =alength-blength;
        while(delta-- >0){
            apointer =apointer.next;
        }

        while(apointer != null){
            if (apointer == bpointer) return apointer;
            else {
                apointer=apointer.next;
                bpointer=bpointer.next;
            }
        }
        return null;
    }

在看题解时发现一种奇妙的思路：

// 法2
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode apointer = headA;
        ListNode bpointer =headB;
        while( apointer != bpointer){
            if (apointer == null) apointer=headB;
            else apointer=apointer.next;

            if (bpointer == null) bpointer =headA;
            else bpointer=bpointer.next;
        }
        return apointer;
    }

这种方法分析如下：

若没有交点，则两个指针完成遍历后会同时到两个链表的结尾。

这种方法代码量比我自己的方法少很多。

python：

    # 法1
    def getIntersectionNode_0(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        apointer = headA
        alength = 0
        while apointer is not None:
            alength = alength + 1
            apointer = apointer.next

        bpointer = headB
        blength = 0
        while bpointer is not None:
            blength = blength + 1
            bpointer = bpointer.next

        if alength < blength:
            temphead = headA
            headA = headB
            headB = temphead
            templength = alength
            alength = blength
            blength = templength

        delta = alength - blength
        apointer = headA
        bpointer = headB
        while (delta > 0):
            delta = delta - 1
            apointer = apointer.next

        while apointer is not None:
            if apointer == bpointer:
                return apointer
            else:
                apointer = apointer.next
                bpointer = bpointer.next
        return apointer

    # 法2
    def getIntersectionNode(self, headA, headB):
        apointer=headA
        bpointer=headB
        while(apointer!=bpointer):
            if apointer is None: apointer=headB
            else: apointer=apointer.next

            if bpointer is None: bpointer=headA
            else: bpointer=bpointer.next
        return apointer

环形链表

这个问题包含两个问题：

有没有环？
如果有的话，环的入口在哪？

解决第一个问题，可以使用快慢指针法：从虚拟头节点开始，一个指针每次移动一步，另一个指针每次移动两部，如果两者相遇则代表有环。为了解释这个方法，引入物理上的相对运动的概念：快指针相对慢指针是一步步接近的，因此如果环的话两者一定相遇。

解决第二个问题，先看下图：

由图可知，从head到入口和从交点到入口的节点数是相同的，因此只要用两枚指针从这两个地方开始遍历链表，两枚指针相遇的地方就是入口。

lc142：142. 环形链表 II

java：

public ListNode detectCycle(ListNode head) {
        ListNode fast =head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            slow=slow.next;
            fast=fast.next.next;
            if (slow==fast){
                ListNode temp1=head;
                ListNode temp2=fast;
                while(temp1 != temp2){
                    temp1=temp1.next;
                    temp2=temp2.next;
                }
                return temp2;
            }
        }
        return null;
    }

python：

    def detectCycle_0(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        fast = head
        slow = head
        while (fast is not None) and (fast.next is not None):
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                temp1 = head
                temp2 = fast
                while temp2 != temp1:
                    temp2 = temp2.next
                    temp1 = temp1.next
                return temp1
        return None

python还可以利用集合的特性完成寻找：

    def detectCycle(self, head):
        visited = set()
        while head is not None:
            if head in visited:
                return head
            visited.add(head)
            head = head.next
        return None

注意：要先把head加入集合后移动head

总结

链表到这里就学完了，今天学习了几种全新的思路，删除第n个节点使用双指针虽然不能降低时间复杂度，但是在常数项规模下更高效（毕竟少一轮遍历）；对于链表相交，除了常规的对齐后寻找外，使用链表合并可以减少不少代码量；环形链表的难点主要在于三部分的长度关系

本文由GarfieldTheOldCat原创，转载请标明

TODO：

递归需要强化