那个做兼职网站好,运动服装商城网站建设,seo网站优化,找衣服款式的网站1. 两个链表第一个公共子节点
LeetCode160
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
图示两个链表在节点 c1 开始相交#xff1a; listA [4,1,8,4,5], listB [5…1. 两个链表第一个公共子节点
LeetCode160
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 listA [4,1,8,4,5], listB [5,6,1,8,4,5]
题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构
1.1. 集合 /*** 方法1通过集合来辅助查找** param headA* param headB* return*/public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {HashSetListNode set new HashSet();// 将第一个链表的每个节点放入set中while (headA ! null) {set.add(headA);headA headA.next;}// 遍历第二个链表中的每个节点判断是否存在于set中while (headB ! null) {if (set.contains(headB))return headB;headB headB.next;}return null;}
1.2. 哈希 /*** 方法2通过Hash辅助查找** param pHead1* param pHead2* return*/public static ListNode findFirstCommonNodeByMap(ListNode pHead1, ListNode pHead2) {// 两个链表的头结点不能为空if (pHead1 null || pHead2 null) {return null;}ListNode current1 pHead1;ListNode current2 pHead2;HashMapListNode, Integer hashMap new HashMap();// 将第一个链表中的每个节点存入 hashmap没有用到hashmap的value只用到了key所以本题使用hashset结构更合适while (current1 ! null) {hashMap.put(current1,null);current1 current1.next;}// 遍历第二个链表判断key是否存在hashmap中while (current2 ! null) {if (hashMap.containsKey(current2)) {return current2;}current2 current2.next;}return null;}
1.3. 栈 /*** 方法3通过栈*/public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {// 定义两个栈 将两个链表的节点存放到两个栈中StackListNode stackA new Stack();StackListNode stackB new Stack();// 将两个链表的节点存放到两个栈中while (headA ! null) {stackA.push(headA);headA headA.next;}while (headB ! null) {stackB.push(headB);headB headB.next;}// 比较两个栈 栈顶的值 若相等则出栈直至找到最后一组相等的结点ListNode pNode null;while (stackA.size() 0 stackB.size() 0) {if (stackA.peek() stackB.peek()) {pNode stackA.pop();stackB.pop();}else {break;}}return pNode;}
2. 回文串
LeetCode234
给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。
示例 1 输入head [1,2,2,1] 输出true
示例 2 输入head [1,2] 输出false
2.1. 全部压栈 /*** 方法2全部压栈** param head* return*/public static boolean isPalindromeByAllStack(ListNode head) {// 定义栈 将链表中结点的值依次压入栈StackInteger stack new Stack();ListNode temp head;while (temp ! null) {stack.push(temp.val);temp temp.next;}// 栈中的值依次出栈与链表中的值依次比较若有一个不一致则不是回文串// 栈中的值出栈顺序为原顺序逆序head从头遍历正好符合回文串定义while (head ! null) {if (head.val ! stack.pop()){return false;}head head.next;}return true;}
2.2. 将所有数据压栈仅弹出一半数据进行比较 /*** 方法3将所有数据压栈仅弹出一半数据进行比较* 因为回文串前半部分的逆序就是后半部分所以只需比较一半数据即可* param head* return*/public static boolean isPalindromeByHalfStack(ListNode head) {if (head null)return true;ListNode temp head;StackInteger stack new Stack();//链表的长度int len 0;//把链表节点的值存放到栈中while (temp ! null) {stack.push(temp.val);temp temp.next;len;}//len长度除以2右移1位左边加0相当于除以2len 1;//然后再出栈while (len-- 0) {if (head.val ! stack.pop())return false;head head.next;}return true;}
3. 合并有序链表
3.1. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1 输入L1 [1,2,4], L2 [1,3,4] 输出[1,1,2,3,4,4]
示例 2
输入L1 [], L2 [] 输出[]
示例 3
输入L1 [], L2 [0] 输出[0]
3.1.1. 基本思路
新建一个链表然后分别遍历两个链表每次都选择最小的结点连接到新链表上。 /*** 方法1最基础的做法* 新建一个链表然后分别遍历两个链表每次都选择最小的结点连接到新链表上。* param list1* param list2* return*/public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 新建一个链表这个新链表有一个虚拟头结点便于处理ListNode newNode new ListNode(-1);// 因为newNode需要移动所以先赋值给res备份一下ListNode res newNode;while (list1 ! null || list2 ! null) {if (list1 ! null list2 ! null) {// 如果第一个链表的值大于第二个链表的值则将第二个链表的值加到新链表newNode上if (list1.val list2.val) {newNode.next list2;list2 list2.next;// 将list2的头指针往后移动一个位置} else if (list1.val list2.val) {newNode.next list1;list1 list1.next;} else {newNode.next list2;list2 list2.next;newNode newNode.next;newNode.next list1;list1 list1.next;}newNode newNode.next; // 将newNode的头指针往后移动一个位置}if (list1 ! null list2 null) { // 此时list2已经为空只需连接list1的值newNode.next list1;list1 list1.next;newNode newNode.next;}if (list1 null list2 ! null) {newNode.next list2;list2 list2.next;newNode newNode.next;}}return res.next;} /*** 方法2比方法1更加精简的实现方法** param l1* param l2* return*/public static ListNode mergeTwoListsMoreSimple(ListNode l1, ListNode l2) {ListNode prehead new ListNode(-1);ListNode prev prehead;while (l1 ! null l2 ! null) {if (l1.val l2.val) {prev.next l1;l1 l1.next;} else {prev.next l2;l2 l2.next;}prev prev.next;}// 最多只有一个还未被合并完直接接上去就行了,这是链表合并比数组合并方便的地方prev.next l1 null ? l2 : l1;return prehead.next;}
3.2. 合并K个链表 /*** 合并K个链表** param lists* return*/public static ListNode mergeKLists(ListNode[] lists) {ListNode res null;for (ListNode list : lists) {res mergeTwoListsMoreSimple(res, list);}return res;}
3.3. 合并两个链表
LeetCode1669
给你两个链表 list1 和 list2 它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除并将list2 接在被删除节点的位置。
下图中蓝色边和节点展示了操作后的结果 请你返回结果链表的头指针。
示例 输入list1 [0,1,2,3,4,5], a 3, b 4, list2 [1000000,1000001,1000002] 输出[0,1,2,1000000,1000001,1000002,5] 解释我们删除 list1 中下标为 3 和 4 的两个节点并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
思路找到链表list1保留部分的尾结点和链表list2的尾结点将两链表连接起来就行了。 public static ListNode mergeInBetween(ListNode list1, ListNode list2, int a, int b) {ListNode pre1 list1,post1 list1, post2 list2;int i 0, j 0;while (pre1 ! null post1 ! null j b 1) {// 找到链表1位置a的前一个位置if (i a - 1) {pre1 pre1.next;i;}// 找到链表1位置b的后一个位置if (j b 1) {post1 post1.next;j;}}// 寻找list2的尾结点while (post2.next ! null){post2 post2.next;}// 链表1尾巴连接链表2头部链2尾部连接链1后半部分的头pre1.next list2;post2.next post1;return list1;}4. 双指针
4.1. 寻找中间结点
LeetCode876
给你单链表的头结点 head 请你找出并返回链表的中间结点。
如果有两个中间结点则返回第二个中间结点。 示例 1 输入head [1,2,3,4,5] 输出[3,4,5] 解释链表只有一个中间结点值为 3 。
示例 2 输入head [1,2,3,4,5,6] 输出[4,5,6] 解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。
思路 慢指针一次移动一个结点快指针一次移动两个结点
public ListNode middleNode(ListNode head) {ListNode slow head;ListNode fast head;if (head null) {return head;}while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;}return slow;}
4.2. 寻找链表的倒数第K个元素
输入一个链表输出该链表中倒数第k个节点。本题从1开始计数即链表的尾节点是倒数第1个节点。
示例 给定一个链表: 1-2-3-4-5, 和 k 2。
输出 4。 /*** 给出k找出该链表倒数第K个结点* 思路fast指针先走到第K个结点然后fast和slow 同时走当fast指向null的时候slow指向倒数第K个结点* param head* param k* return*/public static ListNode getKthFromEnd(ListNode head, int k) {ListNode fast head;ListNode slow head;// 让fast指向第K个结点while (fast ! null k 0){fast fast.next;k--;}// 让fast 和 slow同步移动while (fast ! null) {fast fast.next;slow slow.next;}return slow;}4.3. 旋转链表
LeetCode61
给你一个链表的头节点 head 旋转链表将链表每个节点向右移动 k 个位置。
示例 1 输入head [1,2,3,4,5], k 2 输出[4,5,1,2,3]
思路
先用双指针策略找到倒数K的位置也就是{1,2,3}和{4,5}两个序列之后再将两个链表拼接成{4,5,1,2,3}就行了。具体思路是 因为k有可能大于链表长度所以首先获取一下链表长度len如果然后kk % len如果k 0则不用旋转直接返回头结点。否则
快指针先走k步。慢指针和快指针一起走。快指针走到链表尾部时慢指针所在位置刚好是要断开的地方。把快指针指向的节点连到原链表头部慢指针指向的节点断开和下一节点的联系。返回结束时慢指针指向节点的下一节点。
public ListNode rotateRight(ListNode head, int k) {// 当K为0或者头结点为空的时候直接返回头节点if (k 0 || head null) {return head;}ListNode temp head;// 备份头结点 ListNode fast head;ListNode slow head;int len 0;// 拿到链表长度lenwhile(head ! null) {head head.next;len;}if (k % len 0) {return temp;}// 用快指针找到倒数第K1个节点while((k % len) 0) {k--;fast fast.next;}// 快慢指针同时移动快指针移动到最后一个元素时慢指针指向倒数第K1个节点while(fast.next ! null) {fast fast.next;slow slow.next;}ListNode res slow.next;slow.next null;fast.next temp;return res;}
5. 删除结点
5.1. 删除特定结点
LeetCode203
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。
示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5]
思路
我们创建一个虚拟链表头dummyHead使其next指向head。开始循环链表寻找目标元素注意这里是通过cur.next.val来判断的。如果找到目标元素就使用cur.next cur.next.next;来删除。注意最后返回的时候要用dummyHead.next而不是dummyHead。 public ListNode removeElements(ListNode head, int val) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode cur dummyHead;while (cur.next ! null) {if (cur.next.val val) {cur.next cur.next.next;} else {cur cur.next;}}return dummyHead.next;}
5.2. 删除倒数第n个结点
LeetCode19
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。
示例 1 输入head [1,2,3,4,5], n 2 输出[1,2,3,5] public static ListNode removeNthFromEndByTwoPoints(ListNode head, int n) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode fast head;ListNode slow dummyHead;for (int i 0; i n; i) {fast fast.next;}while (fast ! null) {fast fast.next;slow slow.next;}assert slow.next ! null;slow.next slow.next.next;return dummyHead.next;}
5.3. 删除重复元素
5.3.1. 保留一个重复元素
LeetCode83
给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
示例 1 输入head [1,1,2] 输出[1,2]
思路
由于给定的链表是排好序的因此重复的元素在链表中出现的位置是连续的因此我们只需要对链表进行一次遍历就可以删除重复的元素。具体地我们从指针 cur 指向链表的头节点随后开始对链表进行遍历。如果当前 cur 与cur.next 对应的元素相同那么我们就将cur.next 从链表中移除否则说明链表中已经不存在其它与cur 对应的元素相同的节点因此可以将 cur 指向 cur.next。当遍历完整个链表之后我们返回链表的头节点即可。 另外要注意的是 当我们遍历到链表的最后一个节点时cur.next 为空节点此时要加以判断。 public ListNode deleteDuplicates(ListNode head) {if (head null) {return head;}ListNode cur head;while (cur.next ! null) {if (cur.val cur.next.val) {cur.next cur.next.next;} else {cur cur.next;}}return head;}
5.3.2. 删除所有重复元素
LeetCode82
给定一个已排序的链表的头 head 删除原始链表中所有重复数字的节点只留下不同的数字 。返回 已排序的链表 。
示例 1 输入head [1,2,3,3,4,4,5] 输出[1,2,5] 为了防止开头就有重复的元素这个题搞一个虚拟头结点 public ListNode deleteDuplicates(ListNode head) {if (head null) {return head;}// 使用第三个构造函数直接将虚拟节点连接到头结点headListNode dummyHead new ListNode(0, head);ListNode cur dummyHead;while (cur.next ! null cur.next.next ! null) {if (cur.next.val cur.next.next.val) {int x cur.next.val;// 实在是巧妙while (cur.next ! null cur.next.val x) {cur.next cur.next.next;}} else {cur cur.next;}}return dummyHead.next;}
