1.链表基本操作

一 |链表: 基本操作

24. 两两交换链表中的节点

解析: 链表操作通常新建一个空头节点, 使用两个辅助指针 pre 和 cur，每次交换 cur 和 cur->next 两个结点，交换终止条件为 pre 后面不存在两个未交换结点。

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
  ListNode *dummy = new ListNode(0);
  dummy->next = head;
  //0为新建头节点
  // 0 -> 1 -> 2 -> 3 -> 4
  // pre  cur  next
  ListNode *pre = dummy, *cur = dummy->next;
  while (cur && cur->next) {
      ListNode *next = cur->next;
      pre->next = next;
      cur->next = next->next;
      next->next = cur;
      pre = cur;
      cur = cur->next;
  }

  return dummy->next;
}
};

61. 旋转链表

解析:

1.将链表尾部指向头节点 成环

2.将头节点移动n-k个节点

3.断开连接

/*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(nxet){}
}
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
  if (!head) return nullptr;

  // 尾结点指向头结点
  ListNode *cur = head;
  int n = 1;
  while (cur->next) cur = cur->next, n++;
  cur->next = head;

  // 找到分段点
  for (int i = 0; i < n - k % n; i++) {
      cur = cur->next;
  }

  // 从分段点切开
  head = cur->next;
  cur->next = nullptr;

  return head;
}
};

86. 分割链表

解析: 1 -> 4 -> 3 -> 2 -> 5 -> 2

​ lh 1->2->2 rh 4->3->5

1.定义左右两个链表 , 将小于x的值插入到左链表 , 大于等于x的值插入到右链表

2.将左链表尾指针指向右链表头指针 , 为避免成环把右链表尾指针置为空 , 返回左链表头指针

class Solution {
public:
ListNode* partition(ListNode* head, int x) {
  //定义两个指针分别指向左侧链表和右侧链表
  ListNode* lh=new ListNode(0),*l=lh;
  ListNode *rh =new ListNode(0),*r=rh;

  for(ListNode *cur=head;cur;cur=cur->next){
       if(cur->valnext=cur;}
   else r=r->next=cur;
  }
  l->next=rh->next;
  r->next=nullptr;
  return lh->next;
}
 //2.
 /*ListNode *cur=head;
 while(cur)
 {
     if(cur->valnext=cur;
         l=l->next;
     }else
     {
         r->next=cur;
         r=r->next;
     }
     cur=cur->next;
 }*/

};

328. 奇偶链表

解析:

如果链表为空，则直接返回链表。奇偶链表分离

将原链表拆分成奇数节点链表和偶数节点链表，之后再将两个链表进行连接即可。

//解1.
public:
ListNode* oddEvenList(ListNode* head) {
   if (head == nullptr) {
      return head;
  }
  ListNode *odd=head;
  ListNode *eventhead=head->next;
  ListNode *event=eventhead;

  while(event&&event->next){
      odd->next=event->next;
      odd=odd->next;
      event->next=odd->next;
      event=event->next;
  }
  odd->next=eventhead;
  return head;
}
};


//解2.
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
  ListNode* oddHead = new ListNode(0);
  ListNode* oddTail = oddHead;
  ListNode* evenHead = new ListNode(0);
  ListNode* evenTail = evenHead;

  ListNode* cur = head;

  bool isOdd = true;
  while (cur) {
      if (isOdd) {
          oddTail->next = cur;
          oddTail = oddTail->next;
      } else {
          evenTail->next = cur;
          evenTail = evenTail->next;
      }
      cur = cur->next;
      isOdd = !isOdd;
  }
  oddTail->next = evenHead->next;
  evenTail->next = NULL;

  return oddHead->next;
}
};