【CT】LeetCode手撕—143. 重排链表

本文主要是介绍【CT】LeetCode手撕—143. 重排链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

• 原题连接：143. 重排链表

---

1- 思路

• 模式识别：重排链表 ——> 逆向 ——> ① 找到中间节点 ——> ②逆置 mid.next 链表——> ③遍历

---

2- 实现

⭐143. 重排链表——题解思路

class Solution {public void reorderList(ListNode head) {ListNode mid = findMiddle(head);ListNode leftHead = head;ListNode rightHead = mid.next;mid.next = null;rightHead = reverList(rightHead);while(leftHead!=null && rightHead!=null){// 先记录两链表的下一个结点ListNode leftNext = leftHead.next;ListNode rightNext = rightHead.next;leftHead.next = rightHead;leftHead = leftNext;rightHead.next = leftHead;rightHead = rightNext;}}public ListNode findMiddle(ListNode head){ListNode fast = head;ListNode slow = head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;}return slow;}public ListNode reverList(ListNode head){if(head==null || head.next==null) return head;ListNode cur = reverList(head.next);head.next.next = head;head.next = null;return cur;}
}

---

3- ACM 实现

public class linkResort {static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val = x;}}public static ListNode linkSort(ListNode head){ListNode mid  = findMid(head);ListNode leftHead = head;ListNode rightHead = mid.next;mid.next = null;rightHead = reverse(rightHead);while (leftHead!=null && rightHead!=null) {ListNode leftNext = leftHead.next;ListNode rightNext = rightHead.next;leftHead.next = rightHead;leftHead = leftNext;rightHead.next = leftHead;rightHead = rightNext;}return head;}public static ListNode findMid(ListNode head){ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;}return slow;}public static ListNode reverse(ListNode head){if(head== null || head.next==null) {return head;}ListNode cur = reverse(head.next);head.next.next = head;head.next = null;return cur;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表长度n");int n = sc.nextInt();ListNode head=null,tail=null;System.out.println("输入链表元素");for(int i = 0 ; i < n; i++){ListNode newNode = new ListNode(sc.nextInt());if(head==null){head = newNode;tail = newNode;}else{tail.next = newNode;tail = newNode;}}ListNode forRes = linkSort(head);while(forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}
}

这篇关于【CT】LeetCode手撕—143. 重排链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---