题解 | #重排链表#

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;

• ListNode *next;

• ListNode(int x) : val(x), next(NULL) {}

• };

• /
  //根据题意可知，重新排列的链表按照首尾首尾的形式排列的，因此我们可以先采用deque容器将链表节点存储然后再将其按照首尾i首位的形式重新排列；
  class Solution {
  public:
  void reorderList(ListNode *head) {

    deque<ListNode*> dq;
    while(head)
    {
        ListNode*t=head;
        head=head->next;
        t->next=NULL;
        dq.push_back(t);
  
    }
    ListNode*H=new ListNode(0);
    ListNode*h=H;
    while(!dq.empty())
    {
        h->next=dq.front();
        dq.pop_front();
        h=h->next;
        if(!dq.empty()) 
        {
            h->next=dq.back();
            h=h->next;
            dq.pop_back();
        }
    }
    H->next;

  }
  };