LintCode 练习代码

---

35.翻转链表

/**
 * Definition of ListNode
 * 
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 * 
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /*
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        // write your code here
        ListNode* old, *newnode, * temp;
        if (head ==NULL || head->next == NULL) {
            // 链表空或只有一个元素，无需翻转
            return head;
        }
        newnode = head;
        old = head->next; //尚未翻转的链，初始化为第二个元素
        while (old->next){
            //old后仍有元素时，翻转
            temp = old->next; //temp记忆下一个结点的地址
            old->next = newnode; //指回
            newnode = old; // 后移
            old = temp;
        }
        old->next = newnode; // 最后一个结点的处理
        head->next = NULL;
        return old; 
    }
};

---

165. 合并两个排序链表

class Solution {
public:
    /*
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
        // write your code here
        ListNode *temp = new ListNode(0);
        ListNode *p = temp;
        
        while (l1 && l2){
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
                p= p->next;
            } else {
                p->next = l2;
                l2 = l2->next;
                p = p->next;
            }
        }
        if (l1) {
            p->next = l1;
        }
        else {
            p->next = l2;
        }
        return temp->next;
    }
};

---

96. 链表划分

class Solution {
public:
    /*
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    ListNode * partition(ListNode * head, int x) {
        // write your code here
        ListNode * front,* rear;
        ListNode * p1,* p2;
        p1 = new ListNode(0);
        p2 = new ListNode(0);
        
        ListNode *current = head;
        front = p1;
        rear = p2;
        while (current) {
            if (current->val < x) {
                p1->next = current;
                p1 = p1->next;
            }
            else if (current->val >= x) {
                p2->next = current;
                p2 = p2->next;
            }
            current = current->next;
        }
        p1->next = rear->next;
        p2->next = NULL;
        return front->next;
    }
};

---

166. 链表倒数第n个节点

java语言
一次循环定位倒数第n个结点的方法： 定义两个结点temp1和temp2，初始指向head，temp2先后移n位，而后temp1与temp2一起后移直到temp2移出，此时temp1就定位到了倒数第n个结点。

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */

public class Solution {
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: Nth to last node of a singly linked list. 
     */
    public ListNode nthToLast(ListNode head, int n) {
        // write your code here
        ListNode temp1=head;
        ListNode temp2=head;
        while (n-->0) {
            temp2=temp2.next; // temp2后移
        }
        while (temp2 != null){
            temp2=temp2.next;
            temp1=temp1.next;
        }
        return temp1;
    }
}

---

174. 删除链表中倒数第n个结点

有更优的算法，同时取temp1和temp2两个结点挂到head上，temp2先向后移n次，此后temp1和temp2一起后移，当temp2移出变空时，temp1刚好就位于倒数第n个位置

class Solution {
public:
    /*
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    ListNode * removeNthFromEnd(ListNode * head, int n) {
        // write your code here
        int ct = 0; // 记录结点个数
        ListNode *current = head;
        ListNode *temp = new ListNode;
        while (current) {
            // 一趟循环，统计结点个数
            ct++;
            current = current->next;
        }
        
        if (ct == n){
            // 要删除的是倒数第n个，即第一个
            temp =head;
            head = temp->next;
            delete temp;
            return head;
        }
        
        current = head;
        while (ct - n > 1) {
            // 定位到要删除结点的前一个位置
            ct--;
            current = current->next;
        }
        temp = current->next; // temp为要删除结点
        current->next = temp->next; //前一结点与下一结点挂接
        delete temp;
        return head;
    }
};