反转链表

1、新建链表，头解法

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :            val(x), next(NULL) {    }};*/class Solution {public:    ListNode* ReverseList(ListNode* pHead) {        ListNode* node=pHead;        ListNode* res=NULL;        while(node!=NULL)            {            ListNode* temp=new ListNode(node->val);            temp->next=res;            res=temp;            node=node->next;        }        return res;    }};

2、在原链表直接反转链表，需要记录每一个链表元素反转的后一个元素，否则会断链。

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :            val(x), next(NULL) {    }};*/class Solution {public:    ListNode* ReverseList(ListNode* pHead) {        ListNode* pre=NULL;        ListNode* node=pHead;        ListNode* after=NULL;        while(node!=NULL)        {            after=node->next;        node->next=pre;            pre=node;            node=after;        }        return pre;    }};

 

合并两个排序链表，合并后链表还是有序的（升序）

/*struct ListNode {    int val;    struct ListNode *next;    ListNode(int x) :            val(x), next(NULL) {    }};*/class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)    {        if(!pHead1||!pHead2)            return ((pHead1==NULL)?pHead2:pHead1);        ListNode* node1=pHead1;        ListNode* node2=pHead2;        ListNode* newnode=NULL;        ListNode* iter=NULL;            while((node1!=NULL)&&(node2!=NULL))        {            if(node1->val<=node2->val)            {                if(newnode==NULL)                {                    newnode=node1;                    iter=node1;                    node1=node1->next;                }                else                 {                    iter->next=node1;                    iter=iter->next;                    node1=node1->next;                }            }            else            {                if(newnode==NULL)                {                    newnode=node2;                    iter=node2;                    node2=node2->next;                }                else                 {                    iter->next=node2;                    iter=iter->next;                    node2=node2->next;                }            }        }        if(node1)            iter->next=node1;        else            iter->next=node2;        return newnode;    }};