【代码随想录算法训练营-第四天】【链表】24,19, 面试题 02.07,142

2023-12-13 20:05:47

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

第一遍-递归-小看了一下题解

  • 思路:
    • 读了两遍题目才理解…
    • 相邻节点的交换,这个操作很容易实现,但需要一个tmpNode
    • 因为是链表的题目,没开始思考之前先加了dummyNode,还真管用
    • dummyNode作为了最后返回用的,以及新增preNode作为tmpNode
    • 用递归写是因为不想用循环了…感觉递归写起来好玩一些
    • 小看了一下题解的地方:(其实再给自己多一些debug的次数应该也能试出来)
      • 递归结束条件:|| i.next.next == null这个没有想出来
/*
* 这部分是自己在Idea上写的,用了之前的题目实现的MyLinkedList
* 感觉这样会比在力扣上面写更能熟悉链表一些,而且debug更容易一些
* */
package LinkList;


public class Linklist_test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
//        myLinkedList.addAtHead(4);
        myLinkedList.addAtHead(3);
        myLinkedList.addAtHead(2);
        myLinkedList.addAtHead(1);
        LinklistSolution solution = new LinklistSolution();
        ListNode head = solution.swapPairs(myLinkedList.dummy.next);
        for (; head != null; head = head.next) {
            System.out.println(head.val);
        }
    }
}

class LinklistSolution {
    public ListNode reverseDouble(ListNode head, ListNode preNode, ListNode i, ListNode j) {
        // 交换节点
        preNode.next = i.next;
        i.next = j.next;
        j.next = i;
        if (i.next == null || i.next.next == null) return head.next;
        // 移动节点
        j = i.next.next;
        i = i.next;
        preNode = preNode.next.next;
        return reverseDouble(head, preNode, i, j);
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode preNode = dummy;
        ListNode i = head;
        ListNode j = head.next;
        return reverseDouble(dummy, preNode, i, j);
    }
}
  • 看了一下代码随想录Java的递归题解,嗯,真🐂,我想不出来
    • 示例代码很好的利用了链表是通过指向下一个节点的地址链接的,所以返回newNode可以实现;
// 示例代码
class LinklistSolution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;
        
        return next;
    }
}

19.删除链表的倒数第N个节点

第一遍

  • 思路:
    • 这一题误操作了,忘记先自己想了,直接看题解了…
    • 算是两遍AC吧,第一次fast指针的循环没控制好
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        if (head.next == null) {
            return head.next;
        }
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        for (; fast != null; fast = fast.next) {
            slow = slow.next;
            // fast = fast.next; 第一次提交的时候多写了一个这个,debug的时候才发现不对
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

面试题 02.07. 链表相交

第一遍

  • 思路:
    • 读了第一遍直接写了,第一次开始写循环又出错了…而且出了两个错误
      • 错误1:判断条件写成了A.next != null,导致所有的链表长度都-1,长度为1且相交的时候会有问题;
      • 错误2:没有写A = A.next的修改条件;
    • 第一遍写完,使用的是A.val = B.val的判断条件,不对,发现有val相等,但是答案并不是对应指针;
    • 麻了,又去看题,看了n遍都没看懂;
    • 最后看了题解,结果发现是指针相等(怎么从题中读出的指针相等的?)
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode A = headA;
        ListNode B = headB;
        int lenA = 0, lenB = 0;
        while (A != null) {
            lenA++;
            A = A.next;

        }
        while (B != null) {
            lenB++;
            B = B.next;
        }
        A = headA;
        B = headB;
        int n = lenA >= lenB ? lenA - lenB : lenB - lenA;
        int m = lenA >= lenB ? lenB : lenA;
        if (lenA > lenB) {
            while (n > 0) {
                A = A.next;
                n--;
            }
        } else {
            while (n > 0) {
                B = B.next;
                n--;
            }
        }
        while (m > 0) {
            if (A == B) {
                return A;
            }
            A = A.next;
            B = B.next;
            m--;
        }
        return null;
    }
}

142.环形链表II

第一遍-看题解后一遍过

  • 思路:
    • 20mins的思考,想到了slowNode每次+1,fastNode每次+2;
    • 但这样单纯的移动,会导致两个点相遇的时候不在入口,答案错误;
    • 最后还是看了题解,感觉不太能想得出来;
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
            if (fastNode == slowNode) {
                while (head != fastNode) {
                    head = head.next;
                    fastNode = fastNode.next;
                }
                return head;
            }
        }
        return null;
    }
}

文章来源:https://blog.csdn.net/qq_40691970/article/details/134780151
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。