LeetCode – 143 – 重排链表 – Java – 两种解法 – 细致
题目
解法一(快慢指针 + 反转 + 合并)
利用 双指针 确定 中间的节点,以中间节点为界限,将链表分割为上下两个部分。
随后将 后半部分反转
最后一步 : 合并 l1 和 l2。
方法一代码
/**
* 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 void reorderList(ListNode head) {
if( head == null){
return;
}
// 得到中间节点
ListNode mid = myMidNode(head);
// 分割链表
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next = null;
// 下部分链表 反转
l2 = myReverse(l2);
// 上下两部分链表合并
mergeLinked(l1,l2);
}
public static void mergeLinked(ListNode l1,ListNode l2){
ListNode l1_tmp = null;// 用来记录 l1 的 next
ListNode l2_tmp = null;// 用来记录 l2 的 next
while(l1!=null && l2 != null){
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
public static ListNode myReverse(ListNode head){
ListNode prev = null;
ListNode cur = head;
while(cur!=null){
ListNode curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
return prev;
}
public static ListNode myMidNode(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow =slow.next;
}
return slow;
}
}
解法二 (借助线性表)
将链表存入到 线性表中, 通过下标 进行 插入 尾结点。
代码
/**
* 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 void reorderList(ListNode head) {
if( head == null){
return;
}
List<ListNode> list = new ArrayList<>();
ListNode node = head;
while(node!=null){
list.add(node);
node = node.next;
}
int n = list.size();
int j = n -1;
int i = 0;
while(i < j){
list.get(i).next = list.get(j);
i++;
if(i == j){
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}
附图
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码