链表的定义：

/**

• Definition for singly-linked list.
• struct ListNode {
• int val;
• ListNode *next;
• ListNode(int x) : val(x), next(NULL) {}
• };
  */

1、交换元素

以交换单链表中第m和n号结点为例。
以头节点为第一个结点，保证m>n，且m、n均小于链表长度。
做法是将待交换的两结点的前驱及自身地址记录下来，然后逐个交换。

需要考虑的特殊情况：

• 可能涉及到头节点。这里的处理是建立一个哨兵
• 可能待交换的结点是紧挨着的,这样就不可以简单地交换了，这里进行了特判

class Solution {
public:
    ListNode* swapNode(ListNode* head, int m, int n) {
        ListNode* headTmp = new ListNode(1);
        headTmp->next = head;
        ListNode* pre1 = NULL;
        ListNode* lat1 = NULL;
        ListNode* pre2 = NULL;
        ListNode* lat2 = NULL;
        int counter = 0;
        ListNode* p = headTmp;
        while(p && (counter <= n))
        {
            if(counter == m-1)
                pre1 = p;
            if(counter == m)
                lat1 = p;
            if(counter == n-1)
                pre2 = p;
            if(counter == n)
                lat2 = p;
            ++counter;
            p = p->next;
        }
        ListNode* tmp = lat1->next;
        lat1->next = lat2->next;
        pre1->next = lat2;
        if(n == m+1)//结点紧挨着的情况
        {
            lat2->next = lat1;
        }
        else
        {
            pre2->next = lat1;
            lat2->next = tmp;
        }
        ListNode* newHead = headTmp->next;
        delete headTmp;
        return newHead;
    }
};

2、链表反转

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

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

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

大体思路：采用三指针，前两个指针用于反转，后一个指针用于记录next的值

注意：反转如果涉及到头或尾节点需要特殊处理.

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* headTmp = new ListNode(1);
        headTmp->next = head;//设置哨兵
        ListNode *pre = NULL;
        ListNode *rear = NULL;
        ListNode *p = headTmp;
        int counter = 0;
        while(p && (counter + 1 < m))
        {
            ++counter;
            p = p->next;
        }//循环后p指向反转部分的前驱(第m-1个结点)
        pre = p;
        p = p->next;
        rear = p;//反转部分的头部(第m个结点，也就是反转后的尾部)
        ++counter;
        ListNode *p1 = p->next, *p2;
        if(!p1)//m=n=链表长度，啥也不用做
        {
            delete headTmp;
            return head;
        }
        p2 = p1->next;
        while(p2 && (counter < n))//交换第counter和第counter+1个结点
        {
            p1->next = p;
            p = p1;
            p1 = p2;
            p2 = p2->next;
            counter++;
        }//p为第n个结点，p1为尾结点的后继
        if(n > counter )
        {
            p1->next = p;
            p = p1;
            p1 = p2;
        }
        pre->next = p;
        rear->next = p1;
        ListNode* newhead = headTmp->next;
        delete headTmp;
        return newhead;
    }
};

下面是在leetcode上找到的比较优美的代码：

范例1：
这个不需要特判，太舒服了。
需要弄明白如何迭代（建议画画图）。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* headTmp = new ListNode(1);
        headTmp->next = head;
        ListNode* pre = headTmp;
        int counter = 0;
        while(counter < m - 1)
        {
            ++counter;
            pre = pre->next;
        }//pre定位到m-1的位置
     ListNode* back = pre->next;
    while(counter < n-1)
    {
        ListNode* front = back->next;//back->next指向反转部分的最后一个结点
        back->next = front->next;//front->next是下一个反转的结点
        front->next = pre->next;//pre->next指向反转之后、反转部分的尾结点
        pre->next = front;
        ++counter;
    }
        return headTmp->next;
    }
};