自学内容网 自学内容网

反转链表 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)!