版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/52176455
翻译
给定一个链表: L0→L1→…→Ln-1→Ln,
将其重排序成: L0→Ln→L1→Ln-1→L2→Ln-2→…
你必须不改变节点的值就地解决这个问题。
例如,给定{1,2,3,4},重排序成{1, 4, 2, 3}。
原文
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}.
分析
这里我用了3个步骤:
1,找出中间的节点(p1)
1 2 3 4 5 此时中间节点为3
1 2 3 4 5 6 此时中间节点仍为3
ListNode *p1 = head, *p2 = head;
while (p2->next != NULL && p2->next->next != NULL) {
p1 = p1->next;
p2 = p2->next->next;
}
2,对后半部分进行逆序处理
1 2 3 4 5 处理成: 1 2 3 5 4
1 2 3 4 5 6 处理成: 1 2 3 6 5 4
p1->next = reverseList(p1->next);
ListNode* reverseList(ListNode* head) {
return reverseListIter(head, NULL);
}
ListNode* reverseListIter(ListNode* head, ListNode* newHead) {
if (head == NULL) return newHead;
ListNode* nextNode = head->next;
head->next = newHead;
return reverseListIter(nextNode, head);
}
关于这一部分可以看这篇:
LeetCode 206 Reverse Linked List(反转链表)(四步将递归改写成迭代)(*)
3,关键是这一部分
1 2 3 5 4 处理成: 1 5 2 4 3
1 2 3 6 5 4 处理成: 1 6 2 5 3 4
ListNode *m1 = head;
while (m1->next != NULL && m1->next->next != NULL) {
ListNode *t = m1->next;
m1->next = p1->next; // line 1
p1->next = m1->next->next; // line 2
m1->next->next = t; // line 3
m1 = t; // line 4
}
1(m1) -> 2(t) -> 3(p1) -> 5 -> 4 -> null
(# line 1, line 2) ->
1(m1) -> 5 -> 4 -> null, 3(p1) -> 4 -> null (此时的t是 2 -> 3 -> 4 -> null)
(# line 3) ->
1(m1) -> 5 -> 2(t) -> 3(p1) -> 4 -> null
(# line 4) ->
1 -> 5 -> 2(m1) -> 3(p1) -> 4 -> null
(# line1, line 2)
1 -> 5 -> 2(m1) -> 4, 3(t,p1) -> null
(# line 3)
1 -> 5 -> 2(m1) -> 4 -> 3(t, p1) -> null
(# line 4)
1 -> 5 -> 2 -> 4 -> 3(m1, t, p1) -> null
over
关于 1 2 3 6 5 4 的情况大家可以自己试试
代码
相关的文章:如何用Emacs编译C++代码
我这代码是在Emacs上写的,Emacs又是在Terminal中的,博客也是在Emacs中写的。