1)一个带头结点的单链表L中存放了一组非0的整数，编写一算法实现将所有正数放在前面，负数放在后面。

### 回答1：
可以使用双指针法，一个指针从头开始扫描，一个指针从尾部开始扫描，当两个指针相遇时停止。具体实现如下：

void sortList(ListNode* head) {
if (head == nullptr) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
if (p->val > 0) {
p = p->next;
q = q->next;
} else if (q->val > 0) {
int tmp = p->val;
p->val = q->val;
q->val = tmp;
p = p->next;
q = q->next;
} else {
q = q->next;
}
}
}

其中，p指针指向第一个非正数，q指针指向第一个正数，当q指针指向的节点的值大于0时，交换p和q指针指向的节点的值，并将p和q指针都向后移动一位；当q指针指向的节点的值小于等于0时，只将q指针向后移动一位。最终，所有正数都被放在了前面，所有负数都被放在了后面。

### 回答2：
算法思路如下：
1) 定义两个指针，分别为p和q，初始时p和q都指向头结点。
2) p指针用于遍历链表，q指针用于记录当前最后一个正数的位置。
3) 在遍历过程中，如果p指针指向的节点的值是正数，则将该节点移到q指针的后面，并更新q指针的位置。否则，p指针继续向后移动。
4) 遍历结束后，将q指针的下一个节点（第一个负数节点）与头结点的下一个节点（第一个正数节点）交换位置，即可将正数和负数分开。

具体实现如下：

def separate_positive_and_negative(L):
    if L is None or L.next is None:
        return L
    
    p = L.next  # p指针指向第一个节点
    q = L  # q指针指向头结点
    
    # 将正数放在前面，负数放在后面
    while p is not None:
        if p.val > 0:  # 如果节点的值是正数
            # 将该节点移到q指针的后面
            temp = p.next  # 暂存p的下一个节点
            p.next = q.next
            q.next = p
            q = p  # 更新q指针的位置
            p = temp  # p指针继续向后移动
        else:
            p = p.next
    
    # 交换第一个正数节点和第一个负数节点的位置
    first_positive = L.next
    first_negative = q.next
    L.next = first_negative
    q.next = first_positive
    
    return L

该算法的时间复杂度为O(n)，其中n为链表的长度。

### 回答3：
算法思路：

1) 使用两个指针positive和negative分别指向链表L的头结点，初始化为null。
2) 从头结点开始遍历链表L，如果当前节点的值大于0，则将其插入到positive指针所指节点的后面，并更新positive指针的位置。如果当前节点的值小于0，则将其插入到negative指针所指节点的后面，并更新negative指针的位置。
3) 遍历完链表L后，将negative指针所指节点的后继指针指向null，表示链表的末尾。
4) 如果positive指针为null，说明链表中没有正数，则算法结束；否则，将negative指针所指节点的后继指针指向positive指针所指节点，表示将正数部分和负数部分连接起来。
5) 返回修改后的链表L。

算法实现：

void rearrangeList(ListNode* L) {
    ListNode* positive = NULL; // 指向正数链表的指针
    ListNode* negative = NULL; // 指向负数链表的指针

    ListNode* cur = L->next; // 从头结点的后继节点开始遍历链表

    while (cur != NULL) {
        ListNode* next = cur->next; // 保存当前节点的后继节点的指针

        if (cur->val > 0) {
            cur->next = positive;
            positive = cur;
        } else {
            cur->next = negative;
            negative = cur;
        }

        cur = next;
    }

    if (positive == NULL) { // 链表中没有正数
        L->next = negative;
    } else { // 链表中有正数
        L->next = negative;
        while (negative->next != NULL) {
            negative = negative->next;
        }
        negative->next = positive;
    }
}

时间复杂度：O(n)，其中n为链表的长度。算法需要遍历整个链表一次，进行常数次的插入和更新操作。

空间复杂度：O(1)，算法只需要使用常数个指针用于辅助操作，不需要额外的空间。