단일 체인 표 반전 (세 가지 방법 총화)

제목: 링크 를 입력 하고 링크 를 반전 시 킨 후 링크 의 모든 요 소 를 출력 합 니 다.
방법 1:
사고: 원래 링크 의 머리 에서 노드 를 하나씩 취하 고 새로운 링크 의 머리 에 삽입 합 니 다.
(1)

struct ListNode{
        int val;
        struct ListNode *next;
        ListNode(int x):val(x),next(NULL){}
};

class Solution{
public:
        ListNode* ReverseList(ListNode*pHead){
                ListNode* newh=NULL;
                for(ListNode* p=pHead;p;)
                  {
                         ListNode* tmp=p->next;
                         p->next=newh;
                         newh=p;
                         p=tmp;
                  }
                 return newh;
}
};

(2)

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL)
            return pHead;      
        ListNode *res,*cur,*next;
        res = new ListNode(-1);
        cur = pHead;
        next = cur->next;
        while(cur != NULL)
            {       
            ListNode *first = res->next;
            cur->next = first;
            res->next = cur;

            cur = next;
            next = next->next;       
        }   
        return res->next;  
    }
};

방법 2:
사고방식: 매번 원래 의 첫 번 째 결점 뒤의 그 결점 을 새로운 표 두 뒤에 놓는다.  예 를 들 면 1, 2, 3, 4, 5.  첫 번 째: 첫 번 째 결점 1 뒤의 결점 2 를 새 표 뒤에 놓 고 2, 1, 3, 4, 5 로 변 한다.  두 번 째: 첫 번 째 결점 1 뒤의 결점 3 을 새 표 뒤에 놓 고 3, 2, 1, 4, 5 로 변 한다.  ……  첫 번 째 결점 1, 뒤에 결점 이 없 을 때 까지.  코드 는 다음 과 같 습 니 다:

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead == NULL)
            return pHead;

        ListNode *res,*first,*temp;
        res = new ListNode(-1);
        res->next = pHead;

        first = res->next;       //first         ，    
        while(first->next!=NULL) //temp     
            {
            temp = first->next;
            first->next = temp->next;
            temp->next = res->next;
            res->next = temp;          
        }

        return res->next;
    }
};

방법
세 번 째 방법 은 두 번 째 방법 과 차이 가 많 지 않다. 두 번 째 방법 은 뒤의 결점 을 머리 결점 의 뒤로 이동 시 키 는 것 이다. 세 번 째 방법 은 앞의 결점 을 원래 의 마지막 결점 의 뒤로 이동 시 키 는 것 이다. 사고방식 과 두 번 째 방법 은 차이 가 많 지 않 으 면 코드 를 붙 이지 않 는 다.