反转链表 II（leetcode）

题目链接：. - 力扣（LeetCode）

分享两道解题思路：

第一个：

将left~right之间的节点翻转，首先left前的节点的next置为空，right的指针置为空，

然后拼接

   

p1指的是left前面的一个  p1->next = NULL

p2指的是left

p3指的是right  p3->next = NULL;

p4指的是right后的一个

注意：当p1为空时，即left为1，返回值就不是头结点，而是翻转后的第一个节点

 struct ListNode* reserve( struct ListNode* phead )
 {
    if( !phead || !phead->next )return phead;
    struct ListNode* p1 = NULL;
    struct ListNode* p2 = phead;
    struct ListNode* p3 = phead->next;
    while( p2 )
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        if( p3 )p3 = p3->next;
    }
    return p1;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    if( left == right )
    return head;
    int i = 0;
    struct ListNode* phead = head;
struct ListNode* p1 = NULL;
struct ListNode* p2 = NULL;
struct ListNode* p3 = NULL;
struct ListNode* p4 = NULL;
for( i = 1 ; head ; i++)
{
if( i == left - 1 )
{
p1 = head;
struct ListNode* temp ;
temp = head->next;
head = temp;
}
else if( i == left )
{
p2 = head;
head = head->next;
}
else if( i == right  )
{
p3 = head;
p4 = head->next;
struct ListNode* temp ;
temp = head->next;
head->next = NULL;
head = temp;
}
else
{
head = head->next;
}
}
struct ListNode* temp  = reserve(p2);
if( p1 )
p1->next = temp;
p2->next = p4;
if( !p1 )return temp;
return phead;
}

思路二：

栈处理：将left~right之间的节点存入栈中，然后再将栈顶数据倒出

要有哨兵节点：原因：当left为1时，头结点改变（会影响返回值），为了不让头结点改变，增加头结点

typedef struct Stack
{
struct ListNode** arr;
int size;
int top;
}ST;
void StackInit(ST* obj)
{
obj->size = 0;
obj->top = -1;
obj->arr = (struct ListNode**)malloc(sizeof(struct ListNode*)*10000);
}
void StackPush( ST* obj,struct ListNode* temp )
{
obj->arr[++obj->top] = temp;
obj->size++;
}
void StackPop( ST* obj )
{
obj->size--;
obj->top--;
}
bool StackIsEmpty(ST* obj )
{
return obj->size==0;
}
struct ListNode* StackTop( ST* obj )
{
return obj->arr[obj->top];
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    ST obj;
StackInit(&obj);
struct ListNode* phead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* temp = phead;
phead->next = head;
struct ListNode* p = head;
int i = 1;
while( p )
{
if( i == left )
{
while( i <= right  )
{
i++;
StackPush(&obj,p);
p = p->next;
}
while( !StackIsEmpty(&obj) )
{
phead->next = StackTop(&obj);
phead = phead->next;
StackPop(&obj);
}
phead->next = p;
}
else
{
i++;
phead->next = p;
phead = phead->next;
p = p->next;
}
}
return temp->next;
}

原文地址：https://blog.csdn.net/wx20041102/article/details/137524555

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！