反转链表 & 找链表的入环点 & 找链表的倒数第k个节点 & 使得数组中奇数位于偶数之前

反转链表：         1. 用头插来实现         2. 用栈来实现(递归)         3. 三个指针，一个表示本节点，一个表示前驱，一个表示后继  

找链表的入环点:

       第一步确认是否有环：

            方法：快慢指针：                        一个走得快，一个走的慢，当慢的能追上快的就是有环                         如果当走得快的走到了结尾，则表示没环。

       第二步找入环点：

              方法1. 一个指针先从头走环的大小个步，然后第二个和第一个一起走，则相遇时就是入环点               方法2. 快慢指针相遇点到入环点的距离==从头开始到入环点的距离

确定是否有环的代码如下：

ListNode* MeetingNode(ListNode* pHead) //找是否有环 { if (pHead == NULL) return NULL; ListNode *pslow = pHead->next;//慢 if (pslow == NULL) return NULL; ListNode* pfast = pslow->next;//快 while (pfast != NULL && pfast->next != NULL) { if (pslow == pfast) return pslow; pslow = pslow->next; pfast = pfast->next->next; } return NULL; }

 

找链表的倒数第k个节点：

分析：

      方法1，先计算链表长度，在找第k个节点       方法2. 两个指针，一个先走k-1步；第k步开始时，两个指针一块走；当先走的到尾时，则后走的所在位置就是第 k个节点

注意：链表可能总长度都不为 k，所以针对这个情况要处理

代码实现如下：

ListNode *FindKthToTail(ListNode* plist, unsigned int k) { if (plist == NULL || k == 0) return NULL; ListNode *pAheaad = plist; ListNode *pBehind = NULL; int i = 0; for (unsigned int i = 0; i < k - 1; i++) //先走k-1步 { if (pAheaad->next != NULL) pAheaad = pAheaad->next; else //链表长度没有k-1长度个 return NULL; } pBehind = plist; while (pAheaad->next != NULL) //后续还有数据 { pBehind = pBehind->next; pAheaad = pAheaad->next; } return pBehind; //返回后走的节点，即为倒数第k个节点 }

 

 

使得数组中奇数位于偶数之前：

分析：使用二分的思想

代码实现：

void reOrderArray(int *arr, int len) { int index1 = 0; int index2 = len - 1; while (index1 < index2) { while (index1 < index2 && (arr[index1] & 0x1) == 1) index1++; while (index1 < index2 && (arr[index2] & 0x1) == 0) index2--; if (index1 < index2) { int tmp = arr[index1]; arr[index2] = arr[index1]; arr[index1] = tmp; } } }

扩展：我们可以通过函数指针来是实现范式，使得此代码的结构不变情况下完成更多的不同需求"分边"任务。