【leetcode刷题】T108-重排链表
【题目】
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 :
给定链表 ->->->, 重新排列为 ->->->3.
示例 :
给定链表 ->->->->, 重新排列为 ->->->->3.
【思路】
将链表分为前后两个部分list1和list2，再将后半部分list2的链表进行翻转，接着按照题目要求生成新链表即可。
【代码】
python版本
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
# 链表分为前后两部分
p = head
q = head
while q.next and q.next.next:
p = p.next
q = q.next.next
# 后半部分的链表翻转
head2 = p
q = p.next
r = p.next
while q:
r = q.next
q.next = p
p = q
q = r
head2.next = None
head2 = p
# 链表插入
p = head
q = head2
while p and q:
r = p.next
p.next = q
s = q.next
q.next = r
p = r
q = s
C++版本
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next)
return;
// 切成两个链表
ListNode* p = head;
ListNode* q = head;
while(q->next && q->next->next){
p = p->next;
q = q->next->next;
}
ListNode* head2 = p;
// 链表后半部分翻转
q = p->next;
ListNode* r = p->next;
while(q){
r = q->next;
q->next = p;
p = q;
q = r;
}
head2->next = NULL;
head2 = p;
//组成新链表
p = head;
q = head2;
ListNode* s = NULL;
while(p && q){
r = p->next;
p->next = q;
s = q->next;
q->next = r;
p = r;
q = s;
}
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读