【剑指Offer】026. 重排链表

给定一个单链表L的头节点head，单链表L表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public void ReorderList(ListNode head) { // 思路：将列表中的所有节点添加到栈中，每次插入时就从栈中取出 // 边界条件：head不能为null或者head.next不能为null if (head == null || head.next == null) return; // 将所有的节点压入栈中 Stack<ListNode> nodeStack = new Stack<ListNode>(); // 定义一个peekNode指向栈顶节点 ListNode peekNode = head; while (peekNode != null) { nodeStack.Push(peekNode); peekNode = peekNode.next; } peekNode = nodeStack.Peek(); // 定义一个preNode指向当前的前一个执行了插入的节点，初值为null ListNode preNode = null; // 定义一个nextNode指向下一个需要执行插入的节点，初值为head ListNode nextNode = head; // 临时节点 ListNode tmpNode = null; // 进行一个while循环，循环条件为preNode不能等于栈顶节点或者nextNode不能等于栈顶节点 while ( preNode != peekNode && nextNode != peekNode) { tmpNode = nextNode.next != peekNode ? nextNode.next : null; // 执行插入操作 preNode = nextNode; nextNode.next = peekNode; peekNode.next = tmpNode; nodeStack.Pop(); peekNode = nodeStack.Peek(); nextNode = tmpNode; } // 质空尾部 if(nextNode != null) nextNode.next = null; } }