# 链表的变形

## September 07, 2016

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

1.迭代:迭代的方法就是遍历整个链表，将指向下一结点的指针改变方向，要注意的是因为单链表无法直接找到某个结点的前驱，所以我们需要三个指针，用来记录当前结点，当前节点的后继和其后继的后继，代码如下:

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
}
};


2.递归:

n1 → … → nk-1 → nk → nk+1 ← … ← nm


head->next-next=head;


/*Recursion*/
struct ListNode* reverseList(struct ListNode* head) {
return p;
}



# 143. Reorder List

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}.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
struct ListNode * reverseList(struct ListNode *head){
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
}
public:
return;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
}

right=slow->next;
slow->next=NULL;/*从中间截断*/

right=reverseList(right);
qmove=right;
int index=0;
/*对于奇数个和偶数个要分两种情况*/
while(pmove&&qmove){
if(index%2==0){
struct ListNode * next=pmove->next;
pmove->next=qmove;
pmove=next;
}
else{
struct ListNode * next=qmove->next;
qmove->next=pmove;
qmove=next;
}
index++;
}
}
};


# 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
int len=1;
while(pmove->next){
pmove=pmove->next;
len++;
}
k=len-k%len;
while(k){
pmove=pmove->next;
k--;
}
pmove->next=NULL;
}


# 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

Given 1->2->3->4->5->NULL,

return 1->3->5->2->4->NULL.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(even&&even->next){
odd->next=even->next;
odd=odd->next;
even->next=odd->next;
even=even->next;
}
}
};


# 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2and x = 3,

return 1->2->2->4->3->5.

1. 结点值小于val，放入链表1 2. 其余情况放入链表2

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
struct ListNode left(0),right(0);
struct ListNode *pLeft=&left,*pRight=&right;
pLeft=pLeft->next;
}
else{
pRight=pRight->next;
}
}
pRight->next=NULL;
pLeft->next=right.next;
return left.next;
}
};


# 24. Swap Nodes in Pairs

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct ListNode dummy(0);
while(ptr2){
if(!ptr2->next)
break;
struct ListNode * nextstart=ptr2->next->next;
ptr2->next->next=ptr2;
ptr1->next=ptr2->next;
ptr2->next=nextstart;
ptr1=ptr2;
ptr2=ptr2->next;
}
return dummy.next;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017