92. 反转链表 II

方法一：

提交代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
// 由于leetcode提交默认的是没有头结点的，故需要内部创建一个头结点方便使用
struct ListNode* reverseBetween(struct ListNode* head, int m, int n)
{
    if(n < m)
        return;
    if(n == m)
        return head;
    struct ListNode h = {0, head}; //设置一个头节点【普通结构体变量】,处理m=1的情况
    struct ListNode* pre = &h;  //指针变量赋值
    struct ListNode *p = pre ->next,*q,*t;
    int i = 1;
    while(i < m)
    {
        pre = p;
        p = p->next;
        ++i;
    }
    t = p;  //t 记录翻转部分的起点
    if(m < n)
    {
         p = p->next;
         ++i;
    }
    while(i <= n)
    {
        q = p;
        p = p->next;
        ++i;
        q->next = pre->next;
        pre->next = q;   // 每次将第一步找到的结点指向反转后的头结点
    }
    t->next = p;  //将反转的起点next指向反转后面的结点
    return h.next;
}

codeblocks中运行代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;
void create(Node *head)
{
    //创建链表 【尾插法】
    Node *temp,*p;
    int x;
    printf("请输入链表元素：\n");
    scanf("%d",&x);
    p = head;   //p为尾结点
    while(x != 9999)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp ->data = x;
        p ->next = temp;
        p = p ->next;
        scanf("%d",&x);
    }
    temp ->next = NULL;
}
void input(Node *head)
{
    Node *p = head ->next;  //p为工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
int reverseBetween(Node *head,int m,int n)
{
    if(n < m)
        return 0;
    if(n == m)
        return head;
    Node *pre,*p,*q,*t;
    int i = 1;
    p = head->next;
    pre = head;
    while(i < m)
    {
        pre = p;
        p = p->next;
        ++i;
    }
    t = p;  //t 记录翻转部分的起点
    if(m < n)
    {
         p = p->next;
         ++i;
    }
    while(i <= n)
    {
        q = p;
        p = p->next;
        ++i;
        q->next = pre->next;
        pre->next = q;   // 每次将第一步找到的结点指向反转后的头结点
    }
    t->next = p;  //将反转的起点next指向反转后面的结点
    return head;
}
int main()
{
    Node * head;
    head = (Node *)malloc(sizeof(Node));  //head为头结点
    head ->data = NULL;
    head ->next = NULL;
    create(head);
    input(head);
    printf("\n逆置后：\n");
    head = reverseBetween(head,2,5);
    input(head);
}

方法二：

提交代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
    if(m == n)
        return head; // 不用管的情况
    struct ListNode h = {0, head}; //设置一个头节点,处理m=1的情况
    struct ListNode* p = &h;  //指针变量赋值
    struct ListNode* tail;
    for(int i = 1; i <= n; i++)
        if(i < m) // p指向第n-1个节点位置
            p = p->next;
        else if(i == m) // tail指向第第n个节点，这个节点反转后处在反转部分的最后一个
            tail = p->next;
        else { //每次将tail后面一个节点拿出来，放在item后面
            struct ListNode* item = tail->next;
            tail->next = tail->next->next;
            item->next = p->next;
            p->next = item;
        }
    return h.next;
}

codeblocks中运行代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;
void create(Node *head)
{
    //创建链表 【尾插法】
    Node *temp,*p;
    int x;
    printf("请输入链表元素：\n");
    scanf("%d",&x);
    p = head;   //p为尾结点
    while(x != 9999)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp ->data = x;
        p ->next = temp;
        p = p ->next;
        scanf("%d",&x);
    }
    temp ->next = NULL;
}
void input(Node *head)
{
    Node *p = head ->next;  //p为工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
int reverseBetween(Node *head,int m,int n)
{
    if(n < m)
        return 0;
    if(m == n)
        return head; // 不用管的情况
    struct Node* p = head,* tail;
    int i ;
    for(i = 1; i <= n; i++)
        if(i < m) // p指向第n-1个节点位置
            p = p->next;
        else if(i == m) // tail指向第第n个节点，这个节点反转后处在反转部分的最后一个
            tail = p->next;
        else   //每次将tail后面一个节点拿出来，放在item后面
        {
            struct Node* item = tail->next;
            tail->next = tail->next->next;
            item->next = p->next;
            p->next = item;
        }
    return head;
}
int main()
{
    Node * head;
    head = (Node *)malloc(sizeof(Node));  //head为头结点
    head ->data = NULL;
    head ->next = NULL;
    create(head);
    input(head);
    printf("\n反转后：\n");
    head = reverseBetween(head,2,4);
    input(head);
}

扩展：【逆置链表】

例子： 1 2 3 4 5 6 —— > 6 5 4 3 2 1

方法一：

将头结点摘下，然后从一个结点开始，依次前插入到头结点的后面【头插法建立链表】，直到最后一个结点结束为止

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;
void create(Node *head)
{
    //创建链表 【尾插法】
    Node *temp,*p;
    int x;
    printf("请输入链表元素：\n");
    scanf("%d",&x);
    p = head;   //p为尾结点
    while(x != 9999)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp ->data = x;
        p ->next = temp;
        p = p ->next;
        scanf("%d",&x);
    }
    temp ->next = NULL;
}
void input(Node *head)
{
    Node *p = head ->next;  //p为工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
void reverse(Node * head)
{
    Node *p ,*r;  //p为工作指针，r为p的后继
    p = head ->next;
    head ->next = NULL;  //将头结点的next设为NULL
    //依次将元素结点摘下
    while(p != NULL)
    {
        r = p ->next;  // 暂存p的后继
        // 将p结点插入head之后
        p ->next = head ->next;
        head ->next = p;
        p = r;
    }
}
int main()
{
    Node * head;
    head = (Node *)malloc(sizeof(Node));  //head为头结点
    head ->data = NULL;
    head ->next = NULL;
    create(head);
    input(head);
    printf("\n逆置后：\n");
    reverse(head);
    input(head);
}

方法二：

 设定三个指针：pre，p，r指向相邻的结点

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;
void create(Node *head)
{
    //创建链表 【尾插法】
    Node *temp,*p;
    int x;
    printf("请输入链表元素：\n");
    scanf("%d",&x);
    p = head;   //p为尾结点
    while(x != 9999)
    {
        temp = (Node *)malloc(sizeof(Node));
        temp ->data = x;
        p ->next = temp;
        p = p ->next;
        scanf("%d",&x);
    }
    temp ->next = NULL;
}
void input(Node *head)
{
    Node *p = head ->next;  //p为工作指针
    while(p != NULL)
    {
        printf("%d\t",p ->data);
        p = p ->next;
    }
}
void reverse(Node * head)
{
    //将结点指针翻转
    Node *p = head ->next ,*pre,*r = p ->next;
    p ->next = NULL;   // 处理第一个结点
    while(r != NULL)    // r为空，说明p为最后一个结点
        pre = p;
        p = r;
        r = r ->next;
        p ->next = pre;   // p指向前驱pre
    }
    head ->next =p;    // 处理最后一个结点
}
int main()
{
    Node * head;
    head = (Node *)malloc(sizeof(Node));  //head为头结点
    head ->data = NULL;
    head ->next = NULL;
    create(head);
    input(head);
    printf("\n逆置后：\n");
    reverse(head);
    input(head);
}