力扣143. 重排链表
1、C
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void reorderList(struct ListNode* head){ struct ListNode* p = head; int count = 0; while(p){ p = p->next; count++; } if(count<3)return; p = head; for(int i=0;i<(count+1)/2-1;i++){ p = p->next; } struct ListNode *q = p->next; p->next = NULL; p = NULL; while(q){ struct ListNode* r = q->next; q->next = p; p = q; q = r; } q = head; while(p){ struct ListNode* temp1 = q->next; struct ListNode* temp2 = p->next; p->next = q->next; q->next = p; p = temp2; q = temp1; } }
2、C++
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { ListNode *p = head; int count = 0; while(p!=nullptr){ p = p->next; count++; } if(count<3)return; p = head; for(int i=0;i<(count+1)/2-1;i++){ p = p->next; } ListNode *q = p->next; p->next = nullptr; p = nullptr; while(q!=nullptr){ ListNode* r = q->next; q->next = p; p = q; q = r; } q = head; while(p!=nullptr){ ListNode *temp1 = q->next; ListNode *temp2 = p->next; p->next = q->next; q->next = p; p = temp2; q = temp1; } } };
3、JAVA
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { ListNode p = head; int count = 0; while(p!=null){ p = p.next; count++; } if(count<3)return; p = head; for(int i=0;i<(count+1)/2-1;i++){ p = p.next; } ListNode q = p.next; p.next = null; p = null; while(q!=null){ ListNode r = q.next; q.next = p; p = q; q = r; } q = head; while(p!=null){ ListNode temp1 = p.next; ListNode temp2 = q.next; p.next = q.next; q.next = p; p = temp1; q = temp2; } } }
4、Python
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def reorderList(self, head): """ :type head: ListNode :rtype: None Do not return anything, modify head in-place instead. """ p = head count = 0; while(p is not None): p = p.next count += 1 if(count<3):return; p = head for i in range((count+1)/2-1): p = p.next q = p.next p.next = None p = None while(q is not None): r = q.next q.next = p p = q q = r q = head while(p is not None): temp1 = q.next temp2 = p.next p.next = q.next q.next = p p = temp2 q = temp1标签:count,head,ListNode,val,int,next,链表,算法,重排 From: https://www.cnblogs.com/cmkbk/p/17254990.html