删除链表倒数第N个节点
?在自己的版本上参考大佬修改后的代码
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* fast=head;
struct ListNode* slow=head;
while(n--)
fast=fast->next;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next;
}
if(fast==NULL) return head->next;
slow->next=slow->next->next;
return head;
}很奇怪啊，为什么判断条件有fast呢？原来是为了满足一些特殊数据啊！
?
自己写的话要分很多类，但是在这里做判断确实更好！?
?java后序遍历递归回溯法：（来自力扣大佬）
我自己感觉if(num==n)这个条件有点问题，应该是"！="，这样后面才会做；
至于"node==null"的时候是返回0还是返回1，也应该再想想。
public ListNode removeNthFromEnd(ListNode head, int n) {
int traverse = traverse(head, n);
if(traverse == n)
return head.next;
return head;
}
private int traverse(ListNode node, int n) {
if(node == null)
return 0;
int num = traverse(node.next, n);
if(num == n)
node.next = node.next.next;
return num + 1;
}?反转链表?
方法一：三指针迭代
List Reverse(List L){
if(!L) return NULL;
List temp,nxt; //两个光标，nxt用来保存temp后面一个节点，
temp=L->Next; //这里L反而可以变了，因为是尾巴不是头结点，
L->Next=NULL;
while(temp){
nxt=temp->Next;//先用nxt保存
temp->Next=L;//指向L（尾巴），可以理解为入队
L=temp;//队伍尾巴更新（有点像堆栈的top）
temp=nxt;//更新temp的值
}
return L;
}?方法二：递归
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
"调用递推公式反转当前结点之后的所有节点"
"返回的结果是反转后的链表的头结点"
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
反转前N个节点?
递归（java)：?
ListNode topNSuccessor = null;
private ListNode reverseTopN(ListNode head, int n) {
if (n == 1) {
topNSuccessor = head.next;
return head;
}
ListNode newHead = reverseTopN(head.next, n-1);
head.next.next = head;
head.next = topNSuccessor;
return newHead;
}
迭代?（C）：头插法
truct ListNode *reverseBetween(struct ListNode *head, int left, int right) {
// 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
struct ListNode *dummyNode = malloc(sizeof(struct ListNode));
dummyNode->val = -1;
dummyNode->next = head;
"找到起点的前一个节点"
struct ListNode *pre = dummyNode;
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
"开始头插法"
struct ListNode *cur = pre->next;
struct ListNode *next;
for (int i = 0; i < right - left; i++) {
next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummyNode->next;
}
92.反转第a个到第b个节点?
public ListNode reverseBetween(ListNode head, int m, int n) {
if (m == 1) {
return reverseTopN(head, n);
}
ListNode between = reverseBetween(head.next, m-1,n-1);
head.next = between;
return head;
}
ListNode topNSuccessor = null;
private ListNode reverseTopN(ListNode head, int n) {
if (n == 1) {
topNSuccessor = head.next;
return head;
}
ListNode newHead = reverseTopN(head.next, n-1);
head.next.next = head;
head.next = topNSuccessor;
return newHead;
}class Solution {
public ListNode reverseBetween(ListNode head, int left, int right)
{
ListNode temp=head;
List<ListNode> list=new ArrayList<>();"创建数组作为栈"
"全部节点入栈"
while(temp!=null)
{
list.add(temp);
temp=temp.next;
}
"小细节处理left和right,注意这里"
left=left-1;
right=right-1;
for(int i=right;i>left;i--)
{
list.get(i).next=list.get(i-1);"出栈并且反转"
}
"没看得很懂"
list.get(left).next=(right==list.size()-1?null:list.get(right+1));
if(left==0)"如果从头结点开始反转"
{
return list.get(right);
}
else{"不是从头节点开始反转，那么就将段的最右边节点出栈然后接到原链表后"
list.get(left-1).next=list.get(right);
return head;
}
}
}
https://leetcode-cn.com/problems/reverse-linked-list/solution/yi-bu-yi-bu-jiao-ni-ru-he-yong-di-gui-si-67c3/203 移除链表元素
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* dummyHead = malloc(sizeof(struct ListNode));
dummyHead->next = head;
struct ListNode* temp = dummyHead;
while (temp->next != NULL) {
if (temp->next->val == val) {
temp->next = temp->next->next;
"如果一样那么就temp指针在temp->next的基础上后移一格"
}
else {
temp = temp->next;"如果不一样temp后移一格"
}
}
return dummyHead->next;
}????????真是掉到坑里了，一开始这里还去特别设计如果有连续相同的数要怎么删除，其实哪里需要考虑这个 ，直接交给循环了就好了，这里自然而然地会帮你去后移指针。
递归版本：
（等待更新）
奇偶链表?
基本思路：用双指针来爬奇偶点，注意要同时爬，用一个节点来保存偶数链表的头（及原链表的第二个?节点），奇数链表的表头自然就是原始的head了。
struct ListNode* oddEvenList(struct ListNode* head) {
if (head == NULL) {
return head;
}
struct ListNode* evenHead = head->next; "先存下偶数链表的头"
struct ListNode* odd = head; "odd指针指向第一个奇数节点，即头结点"
struct ListNode* even = evenHead; "even指针指向第一个偶数节点，即第二个节点"
while (even != NULL && even->next != NULL) {
odd->next = even->next; "这里用even->next和odd->next->next好像没什么不同"
odd = odd->next; "自我迭代"
even->next = odd->next; "同上"
even = even->next; "同上"
}
odd->next = evenHead;"偶数链表接到奇数链表后"
return head;
}
?ATTETION ：这里要注意while的循环条件，不能换成奇数判断，也不能写"odd->next&&even->next"，这样子写会出错。因为偶数比奇数大，所以我们用偶数来判断是否遍历完。
（这个点吃了大亏）