文章目錄
- ??問題描述：
- ??演算法思想：
- 💯代碼實作：
??問題描述：
??演算法思想：
🥇題目解讀：
- 我們看看此題，是不是 起先一點思路都沒有呀！！！其實此題并不難，關鍵在于我們一定要讀懂題目，題目是這樣把鏈表后半段的val值，移到鏈表的前半段，并且是這樣的 前半段的一個節點 ，后半段一個節點 ，前半段一個節點·····
🥇具體決議：
- 首先鏈表分為兩半，利用快慢指標思想，快指標一次遍歷鏈表中的兩個節點，慢指標一次遍歷鏈表中一個節點，當快指標把鏈表遍歷完時，慢指標恰好指向鏈表的中間節點，然后把中間節點之后的鏈表斷開，生成兩個子鏈表，
- 翻轉中間節點之后的鏈表，因為在題目中
從后向前遍歷鏈表把后半段的鏈表節點插入到前半段節點中,在這里翻轉鏈表的具體步驟不加以贅述，詳細請看博客鏈表習題 - 翻轉鏈表之后，例如看圖說話中，鏈表后半段節點的順序就變成6,5,4,最后從鏈表的前半段鏈表和后半段鏈表的節點開始，逐個把他們的節點相連成為一個新的鏈表，首先把先半段鏈表和后半段鏈表的頭節點1和6連接起來，在把處于在第二個位置節點的2和5連接起來，最后把兩個尾節點連接3和4起來因此最后的鏈表節點順序為1,6,2,5,3,4，
- 如果原鏈表的個數為奇數時，前半段鏈表比后半段鏈表多一個節點，所以說在兩個子鏈表等分連接完成后，前半段鏈表還不能為空，所以在連接的鏈表之后添上多出的節點，
🥇看圖說話：
💯代碼實作：
//翻轉鏈表
public Node reverseList(Node node){
Node newhead = null;
Node cur = node;
while(cur!=null){
//保存節點
Node curNext = cur.next;
cur.next = newhead;
newhead = cur;
cur = curNext;
}
return newhead;
}
public Node reorderList() {
//首先設定快慢指標，快慢指標遍歷鏈表，慢指標一次遍歷一個節點，快指標一次遍歷兩個節點，所以說當快指標把鏈表遍歷
//完時，慢指標剛好走到了鏈表的一半
Node dummy = new Node(0);
dummy.next = head;
Node fast = dummy;
Node slow = dummy;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//找到中間節點，然后從中間斷開鏈表
Node temp = slow.next;
slow.next = null;
return reSortList(head, reverseList(temp),dummy);
}
public Node reSortList(Node node1,Node node2,Node head){
Node prev = this.head;
while(node1 != null && node2 != null){
//保存遍歷節點
Node temp = node1.next;
prev.next = node1; //node2節點連接node1節點
node1.next = node2;//node1節點連接node2節點
prev = node2;// 更新prev
//遍歷子鏈表
node1 = temp;
node2 = node2.next;
}
//如果原鏈表節點個數為奇數時
if(node1!=null){
prev.next = node1;
}
return head;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298944.html
標籤：其他
上一篇：【軟體測驗】上線前的bug，這些bug先留著，之后再改吧
下一篇：Linux安裝python3.8