1->2->3->4->5 ==> 1->5->2->4->3
使用线性表
将节点依次放入集合中，通过索引交换
/**
* 将链表的节点放入顺序表中，这样方便获取最后一个节点
* 1->2->3->4
* 1->4->2->3
*/
public void recordList(ListNode head){
if (head==null) return;
List<ListNode> list=new ArrayList<>();
ListNode node=head;
while (node!=null){
list.add(node);
node=node.next;
}
int i=0,j=list.size()-1;
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; //避免形成环形链表
}
使用栈
/**
* https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
*/
public void recordList2(ListNode head){
if (head==null) return;
Deque<ListNode> stack=new ArrayDeque<>();
ListNode cur=head;
while (cur!=null){
stack.push(cur);
cur=cur.next;
}
cur=head;
ListNode stack_cur=new ListNode(Integer.MAX_VALUE);
while (cur.next!=stack_cur.next){
stack_cur=stack.poll();
stack_cur.next=cur.next;
cur.next=stack_cur;
cur=cur.next.next;
}
stack_cur.next=null; //防止出现环形问题
}
中间节点，加逆序，加合并链表
/**
* 1 -> 2 -> 3 -> 4 -> 5 -> 6
第一步，将链表平均分成两半
1 -> 2 -> 3
4 -> 5 -> 6
第二步，将第二个链表逆序
1 -> 2 -> 3
6 -> 5 -> 4
第三步，依次连接两个链表
1 -> 6 -> 2 -> 5 -> 3 -> 4
寻找链表中点 + 链表逆序 +合并链表
* @param head
*/
public void recordList3(ListNode head){
ListNode middle=middleNode(head);
ListNode middleNext=middle.next;
//反转后半段链表
middle.next=null;
//这是后半段链表
ListNode afterNode= reverseList(middleNext);
//然后进行一次交错插入操作
mergeList(head,afterNode);
}
private void mergeList(ListNode head, ListNode afterNode) {
ListNode tempH;
ListNode tempA;
while (head!=null&&afterNode!=null){
tempH=head.next;
tempA=afterNode.next;
head.next=afterNode;
head=tempH;
afterNode.next=head;
afterNode=tempA;
}
}
public ListNode middleNode(ListNode head) {
if (head==null) return null;
ListNode[] res=new ListNode[100];
int index=0;
while (head!=null){
res[index++]=head; //index指向数组最后一个元素的后一个位置
head=head.next;
}
return res[index/2];
}
public ListNode reverseList(ListNode head) {
ListNode dummy=new ListNode(-100);
dummy.next=head; //dummy模拟带头结点的链表
if (dummy.next==null||dummy.next.next==null){
//只有一个节点或者没有节点
return head;
}
ListNode temp=dummy.next;
while (temp.next!=null){
temp=temp.next; //找到尾结点
}
ListNode last=temp;
while (dummy.next!=last) {
//相当于尾插法，一直往尾部插入头元素
ListNode p=dummy.next;
dummy.next=p.next;
p.next=last.next;
last.next=p;
}
return dummy.next;
}
