贵州易广建设集团网站,域名邮箱申请,新手学做网站,企业网站建设与管理期末考试文章目录 1.链表指定区间翻转2.两两交换链表中的节点 1.链表指定区间翻转
LeetCode 92.反转链表 解法一#xff1a;头插法。利用虚拟节点进行反转#xff0c;因为头节点有可能发生变化#xff0c;比如 left1 那么需要 dummyNode.next 记录头结点#xff0c;使用虚拟头节点… 文章目录 1.链表指定区间翻转2.两两交换链表中的节点 1.链表指定区间翻转
LeetCode 92.反转链表 解法一头插法。利用虚拟节点进行反转因为头节点有可能发生变化比如 left1 那么需要 dummyNode.next 记录头结点使用虚拟头节点可以避免复杂的分类讨论。 先遍历到 left-1 的节点作为 pre 然后节点依次反转。
public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;for(int i0;ileft-1;i){pre pre.next;}ListNode cur pre.next;for(int i0;iright-left;i){ListNode curNext cur.next;cur.next curNext.next;curNext.next pre.next;pre.next curNext;}return dummyNode.next;
}解法二穿针引线法。比方法一复杂点找到 left-1 和 right1 的位置然后直接翻转 left 和 right 区间链表之后拼接。
public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;for(int i0;ileft-1;i){pre pre.next;}ListNode rightNode pre;for(int i0;iright-left1;i){rightNode rightNode.next;}ListNode suss rightNode.next;// 记得置为null不然会连right后面的部分也反转了。rightNode.next null;ListNode ret reverse(pre.next);pre.next.next suss;pre.next rightNode;return dummyNode.next;
}private ListNode reverse(ListNode head){ListNode cur head.next;head.next null;while(cur!null){ListNode curNext cur.next;cur.next head;head cur;cur curNext;}
}2.两两交换链表中的节点
LeetCode 24. 两两交换链表中的节点 类似问题1只不过区间变成相邻两个节点仍然遍历链表找到每个区间的前置节点然后反转。
public ListNode swapPairs(ListNode head) {ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;while(pre.next!null pre.next.next!null){ListNode node1 pre.next;ListNode node2 pre.next.next;node1.next node2.next;node2.next node1;pre.next node2;pre node1;}return dummyNode.next;
}
