leetCode解题报告之Reorder List

素颜马尾好姑娘i 2022-08-26 00:45 171阅读 0赞

**题目：**

Given a singly linked list L: L0→L1→…→Ln\-1→Ln,  
reorder it to: L0→Ln→L1→Ln\-1→L2→Ln\-2→…

You must do this in-place without altering the nodes' values.

For example,  
Given `{1,2,3,4}`, reorder it to `{1,4,2,3}`.

**分析：**

**看到这个题目，我们首先容易想到的就是把链表分成两半，然后把后半部分链表进行逆序一下，之后再和前半部分结合起来就**

**可以将这道题目AC了！**

**两个要解决的问题：**

**1.如何快速的确定链表的中间位置的结点**

**2.如何将一个链表逆序，并且符合要求“You must do this in-place without altering the nodes' values”**

**代码实现：**

package cn.xym.leetcode;
    
    class ListNode {
    	public int val;
    	public ListNode next;
    
    	ListNode(int x) {
    		val = x;
    		next = null;
    	}
    }
    public class ReorderList {
    	public void reorderList(ListNode head) {
    		/*先判断传入的链表是否为空*/
    		if (head == null)
    			return ;
    		
    		/*[快速求出链表的中间结点]通过两个结点，一个走1个步长，一个走2个步长，最后算出链表的中间结点middleNode*/
    		ListNode middleNode = head;
    		ListNode stepNode = head;
    		while (stepNode != null && stepNode.next != null && stepNode.next.next != null){
    			middleNode = middleNode.next;
    			stepNode = stepNode.next.next;
    		}
    		
    		/*将链表中间结点之后的链表（链表的后半部分）逆序*/
    		ListNode T = middleNode.next;
    		middleNode.next = null;
    		if (T == null)
    			return ;
    		ListNode S = T.next;
    		boolean flag = true;
    		while (T != null && S != null){
    			ListNode temp = S.next;
    			S.next = T;
    			if (flag) {
    				T.next = null;
    				flag = false;
    			}
    			T = S;
    			S = temp;
    		}
    		/*完成链表前半部分和逆序后的后半部分的结合！*/
    		while (T != null && head != null){
    			ListNode temp1 = head.next;
    			ListNode temp2 = T.next;
    			head.next = T;
    			T.next = temp1;
    			head = temp1;
    			T = temp2;
    		}
    		
    	}
    	public static void main(String[] args) {
    		ReorderList list = new ReorderList();
    		ListNode node1 = new ListNode(1);
    		ListNode node2 = new ListNode(2);
    		ListNode node3 = new ListNode(3);
    		ListNode node4 = new ListNode(4);
    		ListNode node5 = new ListNode(5);
    		ListNode node6 = new ListNode(6);
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		node4.next = node5;
    		node5.next = node6;
    		node6.next = null;
    		list.reorderList(node1);
    		while (node1 != null){
    			System.out.println(node1.val);
    			node1 = node1.next;
    		}
    	}
    }