当前位置: 首页> 财经> 金融 > 引流推广团队_电商设计素材_站长工具的使用seo综合查询运营_凡科网免费建站

引流推广团队_电商设计素材_站长工具的使用seo综合查询运营_凡科网免费建站

时间:2025/7/11 23:00:27来源:https://blog.csdn.net/hrh1234h/article/details/145959243 浏览次数:0次
引流推广团队_电商设计素材_站长工具的使用seo综合查询运营_凡科网免费建站

 链表题型可分为快慢指针虚拟头节点两种解题技巧。

快慢指针

使用两个指针(快指针和慢指针),以不同的速度遍历链表,解决与链表位置、环检测相关的问题。

反转链表

  • 快慢指针,慢指针一次走一步,快指针一次走两步,直到快指针为null,返回慢指针节点

public ListNode middleNode(ListNode head){ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}

判断回文链表

  • 找到链表中间节点 + 反转后段链表,然后比较前后两段链表是否相等

环形链表

  • 判断是否有环:快慢指针,慢指针一次走一步,快指针一次走两步,如果相遇说明有环

public boolean hasCycle(ListNode head) {ListNode last = head;ListNode fast = head;while (fast != null && fast.next != null){if (fast == last){return true;}fast = fast.next.next;last = last.next;}return false;}
  • 找到环的首个节点:first指针指向头节点,second指针指向当前快指针,两个指针同时遍历到相遇

if (last == fast){ListNode first = head;ListNode second = fast;while (first != second){first = first.next;second = second.next;}return first;
}

删除链表倒数第N个节点

  • 快慢指针,快指针先走n个节点,然后快慢指针同时移动,当快指针为null,删除慢指针。

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dumy = new ListNode(0);dumy.next = head;ListNode last = dumy;ListNode fast = head;for (int i = 0; i < n; i ++){fast = fast.next;}while (fast != null){fast = fast.next;last = last.next;}last.next = last.next.next;return dumy.next;}

虚拟头节点

在链表头部添加一个虚拟节点(dummy node),简化边界条件处理,尤其是涉及头节点操作的问题。

合并两个升序链表

  • 创造虚拟头节点,然后比较两个链表,依次向后添加

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode dump = new ListNode(0);ListNode cur = dump;while (list1 != null && list2 != null){if (list1.val < list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null){cur.next = list1;}if (list2 != null){cur.next = list2;}return dump.next;}

链表相加

  • 创造虚拟头节点,依次相加两链表节点,sum = x + y + carry,carry = sum/10,sum = sum % 10

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dump = new ListNode(0);ListNode cur = dump;int carry = 0;while (l1 != null || l2 != null){int x = 0, y = 0;if (l1 != null){x = l1.val;}if (l2 != null){y = l2.val;}int sum = x + y + carry;carry = sum / 10;sum = sum % 10;cur.next = new ListNode(sum);cur = cur.next;if (l1 != null){l1 = l1.next;}if (l2 != null){l2 = l2.next;}}if (carry == 1){cur.next = new ListNode(carry);}return dump.next;}

两两交换链表中的节点

  • 创造虚拟头节点,创建one节点指向虚拟头节点,two节点 = one.next,three节点 = one.next.next,temp提前存one.next.next.next,然后one.next = three,three.next = two,two.next = temp

public ListNode swapPairs(ListNode head) {ListNode dumy = new ListNode(0);dumy.next = head;ListNode one = dumy;ListNode two;ListNode three;while (one.next != null && one.next.next != null){ListNode temp = one.next.next.next;two = one.next;three = one.next.next;one.next = three;three.next = two;two.next = temp;one = two;}return dumy.next;}

排序链表

  • 归并排序,把当前链表一分为二(找到链表中间节点),再对左右子链表递归排序(合并两个升序链表)

public ListNode sortList(ListNode head) {if (head == null || head.next == null){return head;}ListNode mid = findMiddle(head);ListNode rightHead = mid.next;mid.next = null;ListNode left = sortList(head);ListNode right = sortList(rightHead);return mergeTwoLists(left, right);}private ListNode findMiddle(ListNode head){ListNode slow = head;ListNode fast = head.next;while (fast != null && fast.next != null){slow = slow.next;fast = fast.next;}return slow;}private ListNode mergeTwoLists(ListNode l1, ListNode l2){ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null && l2 != null){if (l1.val < l2.val){curr.next = l1;l1 = l1.next;}else {curr.next = l2;l2 = l2.next;}curr = curr.next;}if (l1 != null){curr.next = l1;}if (l2 != null){curr.next = l2;}return dummy.next;}

其他 

相交链表

  • 两个指针,先遍历出两个链表的长度,然后长链表和短链表同一长度(长链表指针先遍历长度差的节点),最后比较两段链表是否相等

关键字:引流推广团队_电商设计素材_站长工具的使用seo综合查询运营_凡科网免费建站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: