本文主要是介绍92.反转链表---链表(Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解题思路:主要运用了链表的头插法,实现链表的翻转。
1、我们定义两个指针,分别称之为 g(guard 守卫) 和 p(point)。
我们首先根据方法的参数 m 确定 g 和 p 的位置。将 g 移动到第一个要反转的节点的前面,将 p 移动到第一个要反转的节点的位置上。我们以 m=2,n=4为例。
2、将 p 后面的元素删除,然后添加到 g 的后面。也即头插法。
3、根据 m 和 n 重复步骤(2)
4、返回 dummyHead.next
作者:mu-yi-cheng-zhou-2
链接:https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1、我们定义两个指针,分别称之为 pre 和 cur。
我们首先根据方法的参数 left确定 pre和 cur的位置。将 pre移动到第一个要反转的节点的前面,将 cur 移动到第一个要反转的节点的位置上。我们以 left=2,right=4为例。
2、将 cur后面的元素删除,然后添加到 pre的后面。也即头插法。
3、根据 left和 right重复步骤(2)
4、返回 dummy.next
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {ListNode dummy = new ListNode(-1);dummy.next = head;//让虚拟节点指向原链表的头部ListNode pre = dummy;//设置一个指针,指向以虚拟节点ListNode cur = head;//cur指向原节点的头部for(int i = 0;i < left - 1;i++){//找到翻转的区间就行pre = pre.next;cur = cur.next;}for(int i = 0;i < right - left; i++){//然后就可以在翻转区间里进行翻转ListNode temp = cur.next;cur.next = cur.next.next;temp.next = pre.next;pre.next = temp;}return dummy.next;}
}
头插法的复习:
头部插入分为两个步骤:
第1步:把新的节点的next指针指向原先的头节点。
第2步:把新节点变为链表的头节点。
如图的ai节点,原先是指向aj节点的,先把ai节点的next指针指向a1,再把L的next指向ai.
这篇关于92.反转链表---链表(Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!