反转链表——leetcode:92/206题

简单篇

  1. 示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

    c++版

    /**
             * Definition for singly-linked list.
             * struct ListNode {
             *     int val;
             *     ListNode *next;
             *     ListNode(int x) : val(x), next(NULL) {}
             * };
             */
                class Solution {
                   public:
                          ListNode* reverseList(ListNode* head) {
                          ListNode*new_head=NULL;
                          while(head)//(当链表不为空,即还有节点没有反转)
                          {
                          ListNode*next;//  做存储
                          next=head->next;//(保存链表在该反向节点的后一个节点)
                           head->next=new_head;//(链表反向,旧头结点反)
                           new_head=head;//(新头节点后移到刚刚反转的旧节点)
                           head=next;//(旧头结点移动到下一个需要反转的节点)
                          }
                          return new_head;
                        
            
    
      }

    };

在这里插入图片描述
这个比较简单,因为是直接把整个链表反转,如果是把当中的某一段反转呢?

升级篇

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        int list_len=n-m+1;
        ListNode *result=head;
        ListNode*pre_head=NULL;
        while(--m){
            pre_head=head;
            head=head->next;
        }
        ListNode*N_L_last=head;
        ListNode*new_head=NULL;
        while(head&&list_len)
        {
            ListNode*next=head->next;
            head->next=new_head;
            new_head=head;
            head=next;     
            list_len--;
        }
              N_L_last->next=head;
        if(pre_head)
            pre_head->next=new_head;
        else
            result=new_head;
        return result;
        
        
        
        
    }
};

分析:从m到n,m可能为1(从头开始),n也可能为链表长度(到最后)。

一,只需要注意四个关键节点(m-1, m , n , n+1 )其中m-1与n+1可能为不存在的节点。
二,分为两部份处理问题(两边衔接处)
1),如果m=0,则 :result=new_head(直接为反转链表的首元节点)(pre_head此时 为空,没有与new _head建立关系)
如果m!=0, 则 :pre_head=new_head;(将m-1的节点与反转后节点连接)
2)如果n!=表长,反转后的最后一个节点(N_L_last)与n+1节点连接,而此时正好head指向该节点。
如果n=表长,反转后的最后一个节点(N_L_last)的next应该为空,而此时head也为空,就不需要额外处理了。
三 ,最后返回处理完的头结点。

在这里插入图片描述

代码不全,如须查看完整代码,请登入力扣,查看完整版(题号已给出)
作者水平很菜,且是第一次写,希望看完了别伤身体。